Theory of Computing
-------------------
Title : Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression
Authors : Swastik Kopparty and Srikanth Srinivasan
Volume : 14
Number : 12
Pages : 1-24
URL : http://www.theoryofcomputing.org/articles/v014a012
Abstract
--------
In this paper, we study the method of certifying polynomials for
proving AC^0(+) circuit lower bounds. We use this method to show that
Approximate Majority on $n$ bits cannot be computed by AC^0(+) circuits
of size $n^{1 + o(1)}$. This implies a separation between the power of
AC^0(+) circuits of near-linear size and uniform AC^0(+) (and even
AC^0) circuits of polynomial size. This also implies a separation
between randomized AC^0(+) circuits of linear size and deterministic
AC^0(+) circuits of near-linear size.
Our proof, using certifying polynomials, extends the deterministic
restrictions technique of Chaudhuri and Radhakrishnan (STOC 1996),
who showed that Approximate Majority cannot be computed by AC^0
circuits of size $n^{1+o(1)}$. At the technical level, we show that
for every AC^0(+) circuit $C$ of near-linear size, there is a low-
degree polynomial $P$ over $F_2$ such that the restriction of $C$ to
the support of $P$ 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 $\log^{\Theta(d)} s \cdot \log ({1}/{\epsilon})$ on
the degree of $\epsilon$-error approximating polynomials for AC^0(+)
circuits of size $s$ and depth $d$.
Finally, we use these ideas to give a compression algorithm for AC^0(+)
circuits, answering an open question of Chen, Kabanets, Kolokolova,
Shaltiel, and Zuckerman (Computational Complexity 2015).