Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-147 | 8th September 2015 23:44

The Power of Asymmetry in Constant-Depth Circuits



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.

ISSN 1433-8092 | Imprint