Volume 14 (2018) Article 12 pp. 1-24
Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression
Revised: March 20, 2017
Published: August 25, 2018
[PDF (309K)]    [PS (1687K)]    [PS.GZ (358K)]
[Source ZIP]
Keywords: complexity theory, circuit complexity, Boolean complexity, polynomial approximation
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).