Circuit complexity before the dawn of the new millennium

1996/01/01 by Eric Allender · 2 citations
Computer Science · Engineering · #Algorithm #Circuit complexity #Complexity and Algorithms in Graphs #Computer science #Current (fluid) #Electrical engineering #Electronic circuit #Engineering #Epistemology #Frontier #Geography #History #Low-power high-performance VLSI design #Pace #Pessimism #Philosophy #State (computer science) #VLSI and FPGA Design Techniques

paper · doi:10.1007/3-540-62034-6_33

crossref issued 1996/01/01 · crossref published 1996/01/01 · crossref published-print 1996/01/01 · openalex publication_date 1996/01/01 · crossref published-online 2005/06/03 · crossref created 2012/02/26 · crossref deposited 2025/03/21 · crossref indexed 2025/03/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Citations

• Languages that Capture Complexity Classes
• Parity, circuits, and the polynomial-time hierarchy
• On relativized exponential and probabilistic complexity classes
• Languages which capture complexity classes
• On ACC
• BPP has subexponential time simulations unlessEXPTIME has publishable proofs
• Bounded-width polynomial-size branching programs recognize exactly those languages in NC1
• Alternation
• Finite monoids and the fine structure of NC 1
• A Uniform Circuit Lower Bound for the Permanent
• Algebraic methods in the theory of lower bounds for Boolean circuit complexity

Cited by

• Logic Meets Algebra: the Case of Regular Languages
• ACC0 [wikipedia]