Separation of AC${}^0[\oplus ]$ 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 ${\mathrm{AC}}^0[\oplus ]$ basis (unbounded fan-in AND, OR, NOT and…