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.