Theory of Computing
-------------------
Title : A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta
Authors : Daniel Kane
Volume : 9
Number : 17
Pages : 587-592
URL : http://www.theoryofcomputing.org/articles/v009a017
Abstract
--------
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.