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       : https://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).