Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SIZE HIERARCHIES:
Reports tagged with Size hierarchies:
TR12-102 | 16th August 2012
Swastik Kopparty, Srikanth Srinivasan

#### Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ circuits, with applications

In this paper, we introduce and develop the method of certifying polynomials for proving $\mathrm{AC}^0[\oplus]$ circuit lower bounds.

We use this method to show that Approximate Majority cannot be computed by $\mathrm{AC}^0[\oplus]$ circuits of size $n^{1+o(1)}$. This implies a separation between the power of $\mathrm{AC}^0[\oplus]$ circuits of near-linear size and ... more >>>

ISSN 1433-8092 | Imprint