2011/06/01 by Ryan Williams · 2 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Advanced Graph Theory Research #Class (philosophy) #Combinatorics #Upper and lower bounds #Computer science #Discrete mathematics #Algorithm #Mathematics #Artificial intelligence #Mathematical analysis
paper · doi:10.1109/ccc.2011.36
openalex publication_date 2011/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR, NOT, and MODm gates, where m >; 1 is an arbitrary constant. We prove: 1. NTIME[2n] does not have non-uniform ACC circuits of polynomial size. The size lower bound can be strengthened to quasi-polynomials and other less natural functions. 2. ENP, the class of languages recognized in 2O(n)time with an NP oracle, doesn't have non-uniform ACC circuits of 2no(1)size. The lower bound gives a size-depth tradeoff: for every d, m there is a δ >; 0 such that ENPdoesn't have s depth-d ACC circuits of size 2nδwith MODmgates. Previously, it was not known whether EXPNPhad depth-3 polynomial size circuits made out of only MOD6gates. The high-level strategy is to design faster algorithms for the circuit satisfiability problem over ACC circuits, then prove that such algorithms can be applied to obtain the above lower bounds.