A Fixed-Depth Size-Hierarchy Theorem for AC${}^0[\oplus ]$ via the Coin Problem

Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan +2

We prove the first Fixed-depth Size-hierarchy Theorem for uniform AC${}^0[\oplus ]$ circuits; in particular, for fixed $d$, the class ${\mathcal{C}}_{d,k}$ of uniform AC${}^0[\oplus ]$ for…