2026-10-13T07:11:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3846 2024-03-06T09:34:30Z ddc:004 open_access

Certifying polynomials for AC^0(parity) circuits, with applications Kopparty, Swastik Srinivasan, Srikanth Constant-depth Boolean circuits Polynomials over finite fields Size hierarchies 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 near-linear 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 near-linear 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 near-linear 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 \epsilon-approximating polynomials for AC^0(parity) circuits of size s. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Swastik Kopparty and Srikanth Srinivasan 2012 Is Part Of LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2012.36 urn:nbn:de:0030-drops-38467 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.36 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode