TR13-023 Authors: Alexander A. Sherstov

Publication: 6th February 2013 20:46

Downloads: 3497

Keywords:

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 function $\bigwedge_{i=1}^{n}\bigvee_{j=1}^{n}x_{ij}$,

known as the AND-OR tree, has approximate degree $\Omega(n).$ This lower bound is tight

and closes a line of research on the problem, the best previous bound being $\Omega(n^{0.75})$.

More generally, we prove that the function $\bigwedge_{i=1}^{m}\bigvee_{j=1}^{n}x_{ij}$ has approximate degree

$\Omega(\sqrt{mn}),$ which is tight. The same lower bound was obtained independently by Bun

and Thaler (2013) using related techniques.