pdf icon
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
Download article from ToC site:
[PDF (221K)]    [PS (659K)]    [PS.GZ (227K)]
[Source ZIP]
Keywords: AND-OR tree, polynomial approximation, polynomial representations of Boolean functions, 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.