A Uniform Circuit Lower Bound for the Permanent

1994/10/01 by Eric Allender, Vivek Gore · 3 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Advanced Graph Theory Research #Upper and lower bounds #Combinatorics #Circuit complexity #Electronic circuit #Mathematics #Set (abstract data type) #Discrete mathematics #Function (biology) #Algorithm #Topology (electrical circuits) #Computer science #Mathematical analysis #Physics

paper · doi:10.1137/s0097539792233907

openalex publication_date 1994/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

The authors show that uniform families of ACC circuits of subexponential size cannot compute the permanent function. This also implies similar lower bounds for certain sets in PP This is one of the very few examples of a lower bound in circuit complexity whose proof hinges on the uniformity condition; it is still unknown if there is any set in Ntime(2^n^O(1) ) that does not have nonuniform ACC circuits.

Citations

• Languages that Capture Complexity Classes
• The complexity of computing the permanent
• Finite monoids and the fine structure of NC 1
• NP is as easy as detecting unique solutions
• Bounded-width polynomial-size branching programs recognize exactly those languages in NC1
• Alternation

Cited by

• Non-uniform ACC Circuit Lower Bounds
• Circuit complexity before the dawn of the new millennium
• ACC0 [wikipedia]