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       : https://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.