A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)

DOI10.1007/3-540-61332-3_145zbMath1529.68109OpenAlexW1483660078MaRDI QIDQ6142899

Eric W. Allender

Publication date: 29 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61332-3_145

Mathematics Subject Classification ID

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

Cites Work

• A Turing machine time hierarchy
• The complexity of combinatorial problems with succinct input representation
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Parallel computation with threshold functions
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Almost-everywhere complexity hierarchies for nondeterministic time
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• Finite monoids and the fine structure of NC ¹
• Separating Nondeterministic Time Complexity Classes
• A Uniform Circuit Lower Bound for the Permanent
• Quasi-realtime languages
• Natural proofs

This page was built for publication: A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)