## 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 language | English (US) |
---|---|

Article number | 12 |

Journal | Theory of Computing |

Volume | 14 |

DOIs | |

State | Published - 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