Certifying polynomials for AC 0 [⊕] circuits, with applications to lower bounds and circuit compression

Swastik Kopparty, Srikanth Srinivasan

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

In this paper, we study the method of certifying polynomials for proving AC 0 [⊕] circuit lower bounds. We use this method to show that Approximate Majority on n bits cannot be computed by AC 0 [⊕] circuits of size n 1+o(1) . This implies a separation between the power of AC 0 [⊕] circuits of near-linear size and uniform AC 0 [⊕] (and even AC 0 ) circuits of polynomial size. This also implies a separation between randomized AC 0 [⊕] circuits of linear size and deterministic AC 0 [⊕] 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 AC 0 [⊕] 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.

Original languageEnglish (US)
Article number12
JournalTheory of Computing
Volume14
DOIs
StatePublished - 2018

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Keywords

  • Boolean complexity
  • Circuit complexity
  • Complexity theory
  • Lower bounds
  • Majority
  • Polynomial approximation

Fingerprint Dive into the research topics of 'Certifying polynomials for AC <sup>0</sup> [⊕] circuits, with applications to lower bounds and circuit compression'. Together they form a unique fingerprint.

Cite this