Skip to main content

Separation of AC^0[2] Formulas and Circuits

Srikanth Srinivasan ( IIT Bombay )

The question of the relative computational power of formulas and circuits is a classical question in Complexity theory. In this talk, I will talk about a recent result that answers this question in a particular setting.

More precisely, we give the first separation between the power of formulas and circuits of a given depth in the AC^0[2] basis (unbounded fan-in AND, OR, NOT and XOR gates). Our main result shows that, for all d <= log n/log log n, there exist polynomial-size depth-d circuits over this basis that are not equivalent to any depth-d formulas of size n^{o(d)} (moreover, this separation is optimal in that n^{o(d)} cannot be improved to n^{O(d)}). The result is obtained by a combination of new lower and upper bounds for the class of *Approximate Majorities*, that is, defined as Boolean functions {0,1}^n to {0,1} that agree with the Majority function on 3/4 fraction of inputs.

No prior background in circuit complexity will be assumed.

Joint work with Benjamin Rossman (University of Toronto).

 

 

Share this: