
Revised: March 20, 2017
Published: August 25, 2018
Abstract: [Plain Text Version]
In this paper, we study the method of certifying polynomials for proving \ACP circuit lower bounds. We use this method to show that Approximate Majority on n bits cannot be computed by \ACP circuits of size n^{1 + o(1)}. This implies a separation between the power of \ACP circuits of near-linear size and uniform \ACP (and even \AC^0) circuits of polynomial size. This also implies a separation between randomized \ACP circuits of linear size and deterministic \ACP 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 \ACP 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 \ACP circuits of size s and depth d.
Finally, we use these ideas to give a compression algorithm for \ACP circuits, answering an open question of Chen, Kabanets, Kolokolova, Shaltiel, and Zuckerman (Computational Complexity 2015).