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

DOI10.1007/3-540-61332-3_145zbMATH Open1529.68109OpenAlexW1483660078MaRDI QIDQ6142899FDOQ6142899

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

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

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

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

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)