Name
Title | ||
|---|---|---|
Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression. |
Abstract | ||
|---|---|---|
In this paper, we study the method of certifying polynomials for proving AC(0)[circle plus] circuit lower bounds. We use this method to show that Approximate Majority on n bits cannot be computed by AC(0)[circle plus] circuits of size n(1+o(1)). This implies a separation between the power of AC(0)[circle plus] circuits of near-linear size and uniform AC(0)[circle plus] (and even AC(0)) circuits of polynomial size. This also implies a separation between randomized AC(0)[circle plus] circuits of linear size and deterministic AC(0)[circle plus] 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)[circle plus] 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.log(1/epsilon) on the degree of epsilon-error approximating polynomials for AC(0) [circle plus] circuits of size s and depth d. Finally, we use these ideas to give a compression algorithm for AC(0)[circle plus] circuits, answering an open question of Chen, Kabanets, Kolokolova, Shaltiel, and Zuckerman (Computational Complexity 2015). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4086/toc.2018.v014a012 | THEORY OF COMPUTING |
Keywords | Field | DocType |
complexity theory,circuit complexity,Boolean complexity,polynomial approximation,lower bounds,majority | Discrete mathematics,Compression (physics),Polynomial,Circuit complexity,Electronic circuit,Mathematics | Journal |
Volume | Issue | ISSN |
14 | 1 | 1557-2862 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Swastik Kopparty | 1 | 384 | 32.89 |
| Srikanth Srinivasan | 2 | 2 | 3.75 |