A fixed-depth size-hierarchy theorem for AC 0 [⊕] via the coin problem
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh · 2019
In this work we prove the first Fixed-depth Size-Hierarchy Theorem for uniform AC0[⊕]. In particular, we show that for any fixed d, the class Cd,k of functions that have uniform AC0[⊕] formulas of depth d and size nk form an infinite hierarchy. We show this by exhibiting the first class of explicit functions where we have nearly (up to a polynomial factor) matching upper and lower bounds for the class of AC0[⊕] formulas.