We present a family a monotone functions fd :f0; 1g n !f0; 1g 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( p d)). This gives a negative answer to a problem
Paper
Full text
A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta
Semantic Scholar · Computer Science · 2013
Abstract
We present a family a monotone functions fd :f0; 1g n !f0; 1g 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( p d)). This gives a negative answer to a problem
References (6)
06Daniel's early interest in mathematics was strongly influenced by his father, Jonathan Kane, who was himself a professor of mathematics and computer science at the University of Wisconsin-Whitewater2013 · THEORY OF COMPUTING