Volume 14 (2018) Article 12 pp. 1-24

Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression

by Swastik Kopparty and Srikanth Srinivasan

Received: April 18, 2016
Revised: March 20, 2017
Published: August 25, 2018

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

DOI: 10.4086/toc.2018.v014a012

© 2018 Swastik Kopparty and Srikanth Srinivasan
Licensed under a Creative Commons Attribution License (CC-BY)