TR15-147 Authors: Alexander A. Sherstov

Publication: 8th September 2015 23:53

Downloads: 1571

Keywords:

The threshold degree of a Boolean function $f$ is the minimum degree of

a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv\mathrm{sgn}\; p(x)$. Introduced

in the seminal work of Minsky and Papert (1969), this notion is central to

some of the strongest algorithmic and complexity-theoretic results for

constant-depth circuits. One problem that has remained open for several

decades, with applications to computational learning and communication

complexity, is to determine the maximum threshold degree of a polynomial-size

constant-depth circuit in $n$ variables. The best lower bound prior to our

work was $\Omega(n^{(d-1)/(2d-1)})$ for circuits of depth $d$. We obtain a polynomial

improvement for every depth $d,$ with a lower bound of $\Omega(n^{3/7})$ for depth $3$

and $\Omega(\sqrt{n})$ for depth $d\geq4.$ The proof contributes an approximation-theoretic

technique of independent interest, which exploits asymmetry in circuits to

prove their hardness for polynomials.