The approximate degree of a Boolean function $f$ is the least degree ofa real polynomial that approximates $f$ within $1/3$ at every point. We provethat the function $igwedge_{i=1}^nigvee_{j=1}^nx_{ij}$, known as the AND-OR tree , has approximate degree $Omega(n)$. This lower bound istight and closes a line of research on the problem, the best previous boundbeing $Omega(n^{0.75})$. More generally, we prove that the function$igwedge_{i=1}^migvee_{j=1}^nx_{ij}$ has approximate degree$Omega(sqrt{mn}),$ which is tight. The same lower bound was obtainedindependently by Bun and Thaler (2013) using related techniques.
展开▼
