pdf icon
Volume 9 (2013) Article 17 pp. 587-592 [Note]
Special Issue on Analysis of Boolean Functions
A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta
Received: April 23, 2012
Revised: September 18, 2012
Published: June 10, 2013
Download article from ToC site:
[PDF (175K)] [PS (469K)] [Source ZIP]
Misc.:
[About the Author] [HTML Bibliography] [BibTeX]
Keywords: Boolean functions, monotone functions, decision tree
Categories: Boolean functions, monotone functions, decision tree, special issue, Boolean special issue, note
ACM Classification: F.2.3
AMS Classification: 06E30

Abstract: [Plain Text Version]

We present a family a monotone functions $f_d:\{0,1\}^n\rightarrow\{0,1\}$ so that $f_d$ can be computed as a depth-$d$ decision tree and so that $f_d$ disagrees with any $k$-junta on a constant fraction of inputs for any $k = \exp(o(\sqrt{d})).$ This gives a negative answer to a problem circulated independently by Elad Verbin and by Rocco Servedio and Li-Yang Tan.