pdf icon
Volume 14 (2018) Article 12 pp. 1-24
Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression
Received: April 18, 2016
Revised: March 20, 2017
Published: August 25, 2018
Download article from ToC site:
[PDF (309K)] [PS (1687K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
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]

$ \newcommand{\cclass}[1]{{\textsf{#1}}} \newcommand{\ensuremath}[1]{#1} \newcommand{\AC}{\cclass{AC}} \newcommand{\ACP}{\ensuremath{\cclass{AC}^0[\oplus]}} \newcommand{\F}{{\mathbb{F}}} $

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