ECCC-Report TR15-147https://eccc.weizmann.ac.il/report/2015/147Comments and Revisions published for TR15-147en-usTue, 08 Sep 2015 23:53:48 +0300
Paper TR15-147
| The Power of Asymmetry in Constant-Depth Circuits |
Alexander A. Sherstov
https://eccc.weizmann.ac.il/report/2015/147The 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.Tue, 08 Sep 2015 23:53:48 +0300https://eccc.weizmann.ac.il/report/2015/147