Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR13-023 | 6th February 2013 19:36

#### Approximating the AND-OR Tree

TR13-023
Authors: Alexander A. Sherstov
Publication: 6th February 2013 20:46
Keywords:

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 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.

ISSN 1433-8092 | Imprint