Revised: March 20, 2017

Published: August 25, 2018

**Keywords:**complexity theory, circuit complexity, Boolean complexity, polynomial approximation

**Categories:**complexity theory, lower bounds, circuit complexity, polynomials - multivariate, polynomial approximation, compression

**ACM Classification:**F.1.1, F.2.3, G.1.6

**AMS Classification:**68Q15, 68Q17, 68Q15

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