Separation of AC^0[2] Formulas and Circuits
- 14:00 27th April 2017 ( week 1, Trinity Term 2017 )Room 051, Wolfson Building, Parks Road
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).