Approximating the AND-OR Tree.
Alexander A. Sherstov · 2013
ABSTRACT. The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f within 1=3 at every point. We prove that the functionVn iD1 Wn jD1 xij, known as the AND-OR tree, has approximate degree˝.n/: This lower bound is tight and closes a line of research on the problem, the best previous bound being ˝.n0:75/. More generally, we prove that the function