An average-case depth hierarchy theorem for Boolean circuits

DOI10.1109/FOCS.2015.67MaRDI QIDQ6946843zbMATH OpenFDO

Authors Rocco A. Servedio, Li-Yang Tan, Benjamin Rossman

Publication date 5 August 2025

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx) Theory of computing (68Qxx)

Cited in

(3)

• Shrinkage under random projections, and cubic formula lower bounds for AC^0 (extended abstract)
• On small-depth frege proofs for \textsf{PHP}
• On bounded depth proofs for Tseitin formulas on the grid; revisited

This page was built for publication: An average-case depth hierarchy theorem for Boolean circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6946843)