Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
pdf icon
Volume 14 (2018) Article 12 pp. 1-24
Certifying Polynomials for AC0[] 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]
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]

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