Kopparty, Swastik ;
Srinivasan, Srikanth
Certifying polynomials for AC^0(parity) circuits, with applications
Abstract
In this paper, we introduce and develop the method of certifying polynomials for proving AC^0 circuit lower bounds.
We use this method to show that Approximate Majority cannot be computed by AC^0(parity) circuits of size n^{1 + o(1)}. This implies a separation between the power of AC^0(parity) circuits of
nearlinear size and uniform AC^0(parity) (and even AC^0) circuits of polynomial size.
This also implies a separation between randomized AC^0(parity) circuits of linear size and deterministic AC^0(parity) circuits of nearlinear size.
Our proof using certifying polynomials extends the deterministic restrictions technique of Chaudhuri and Radhakrishnan, 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 nearlinear size, there is a low degree variety V over F_2 such that the restriction of C to V 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 Omega\left(\log^{\Theta(d)} s \cdot \log \frac{1}{\epsilon} \right) on the degree of \epsilonapproximating polynomials for AC^0(parity) circuits of size s.
BibTeX  Entry
@InProceedings{kopparty_et_al:LIPIcs:2012:3846,
author = {Swastik Kopparty and Srikanth Srinivasan},
title = {{Certifying polynomials for AC^0(parity) circuits, with applications}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
pages = {3647},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897477},
ISSN = {18688969},
year = {2012},
volume = {18},
editor = {Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3846},
URN = {urn:nbn:de:0030drops38467},
doi = {10.4230/LIPIcs.FSTTCS.2012.36},
annote = {Keywords: Constantdepth Boolean circuits, Polynomials over finite fields, Size hierarchies}
}
2012
Keywords: 

Constantdepth Boolean circuits, Polynomials over finite fields, Size hierarchies 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Issue date: 

2012 
Date of publication: 

2012 