On ACC

1994/12/01 by Richard Beigel, Jun Tarui · 4 citations
Computer Science · Mathematics · #Binary logarithm #Class (philosophy) #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Degree (music) #Discrete mathematics #Function (biology) #Machine Learning and Algorithms #Mathematics #Physics #Root (linguistics) #semigroups and automata theory

paper · doi:10.1007/bf01263423

crossref issued 1994/12/01 · crossref published 1994/12/01 · crossref published-print 1994/12/01 · openalex publication_date 1994/12/01 · crossref created 2005/03/24 · openalex created_date 2019/02/21 · crossref deposited 2024/12/28 · crossref indexed 2026/03/02 · openalex updated_date 2026/07/23

Citations

• Parity, circuits, and the polynomial-time hierarchy
• Bounded-width polynomial-size branching programs recognize exactly those languages in NC1
• Finite monoids and the fine structure of NC 1
• Algebraic methods in the theory of lower bounds for Boolean circuit complexity

Cited by

• Circuit complexity before the dawn of the new millennium
• Non-uniform ACC Circuit Lower Bounds
• Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
• ACC0 [wikipedia]