Volume 9 (2013)
Article 20 pp. 653-663

Approximating the AND-OR Tree

Received: February 12, 2013

Revised: May 25, 2013

Published: June 19, 2013

Revised: May 25, 2013

Published: June 19, 2013

**Keywords:**AND-OR tree, polynomial approximation, polynomial representations of Boolean functions, approximate degree

**Categories:**short, polynomials, polynomials - multivariate, approximation, Boolean functions, AND-OR tree, polynomial approximation, approximate degree

**ACM Classification:**F.0, F.1.3

**AMS Classification:**68Q05, 68Q87

**Abstract:**
[Plain Text Version]

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}^nx_{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}^nx_{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.