Theory of Computing
-------------------
Title     : Approximating the AND-OR Tree
Authors   : Alexander A. Sherstov
Volume    : 9
Number    : 20
Pages     : 653-663
URL       : https://theoryofcomputing.org/articles/v009a020

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