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

DOI10.1007/3-540-61332-3_145MaRDI QIDQ6142899zbMATH OpenOpenAlexFDO

Authors Eric 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

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

Recommendations

• scientific article; zbMATH DE number 1351078
• Uniform proofs of ACC representations
• A Uniform Circuit Lower Bound for the Permanent
• Nondeterministic NC^1 computation
• Nonuniform ACC circuit lower bounds

Cites work

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

Cited in

(1)

• Circuit complexity before the dawn of the new millennium

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

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