2 papers
cs.CC2017
Separation of AC Formulas and Circuits
Benjamin Rossman, Srikanth Srinivasan
This paper gives the first separation between the power of {\em formulas} and {\em circuits} of equal depth in the basis (unbounded fan-in AND, OR, NOT and…
cs.CC2015
An average-case depth hierarchy theorem for Boolean circuits
Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of , , and gates. Our hierarchy theorem says…