Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0

Alexander A. Sherstov, Pei Wu

The threshold degree of a Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}…