A fixed-depth size-hierarchy theorem for AC 0 [⊕] via the coin problem

DOI10.1145/3313276.3316339zbMath1433.68140arXiv1809.04092OpenAlexW2950999115MaRDI QIDQ5212785

S. Venkitesh, Srikanth Srinivasan, Nutan Limaye, Karteek Sreenivasaiah, Utkarsh Tripathi

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1809.04092

zbMATH Keywords

constant-depth circuitshierarchy theorem

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items

Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?, Unnamed Item, A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem], Parity helps to compute majority