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).