Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-102 | 16th August 2012 05:03

Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ circuits, with applications


Authors: Swastik Kopparty, Srikanth Srinivasan
Publication: 16th August 2012 13:59
Downloads: 3638


In this paper, we introduce and develop the method of certifying polynomials for proving $\mathrm{AC}^0[\oplus]$ circuit lower bounds.

We use this method to show that Approximate Majority cannot be computed by $\mathrm{AC}^0[\oplus]$ circuits of size $n^{1+o(1)}$. This implies a separation between the power of $\mathrm{AC}^0[\oplus]$ circuits of near-linear size and uniform $\mathrm{AC}^0[\oplus]$ (and even $\mathrm{AC}^0$ ) circuits of polynomial size. This also implies a separation between randomized $\mathrm{AC}^0[\oplus]$ circuits of linear size and deterministic $\mathrm{AC}^0[\oplus]$ circuits of near-linear size.

Our proof using certifying polynomials extends the deterministic restrictions technique of Chaudhuri and Radhakrishnan, who showed that Approximate Majority cannot be computed by $\mathrm{AC}^0$ circuits of size $n^{1+o(1)}$. At the technical level, we show that for every $\mathrm{AC}^0[\oplus]$ circuit $C$ of near linear size, there is a low degree variety $V$ over $\mathbb{F}_2$ such that the restriction of $C$ to $V$ is constant.

We also prove other results exploring various aspects of the power of certifying polynomials. In the process, we show an essentially optimal lower bound of $\Omega(\log^{\Theta(d)}s \cdot \log (1/\epsilon))$ on the degree of $\epsilon$-approximating polynomials for $\mathrm{AC}^0[\oplus]$ circuits of size $s$.

ISSN 1433-8092 | Imprint