
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
Revised: September 18, 2012
Published: June 10, 2013
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 fd:{0,1}n→{0,1} so that fd can be computed as a depth-d decision tree and so that fd disagrees with any k-junta on a constant fraction of inputs for any k=exp(o(√d)). This gives a negative answer to a problem circulated independently by Elad Verbin and by Rocco Servedio and Li-Yang Tan.