An Average-Case Depth Hierarchy Theorem for Boolean Circuits

DOI10.1145/3095799zbMath1426.68098arXiv1504.03398OpenAlexW1558278838MaRDI QIDQ4640300

Li-Yang Tan, Benjamin Rossman, Rocco A. Servedio, Johan T. Håstad

Publication date: 17 May 2018

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

polynomial hierarchyrandom projectionsrandom oraclesBoolean circuit complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Related Items (5)

Pseudo-Derandomizing Learning and Approximation ⋮ Unnamed Item ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ Fine-Grained Cryptography ⋮ Reflections on Proof Complexity and Counting Principles

This page was built for publication: An Average-Case Depth Hierarchy Theorem for Boolean Circuits