A Casual Tour Around a Circuit Complexity Bound

2011/11/04 by Ryan Williams, Williams, Ryan
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1111.1261

21 pages, 2 figures. An earlier version appeared in SIGACT News, September 2011

arxiv created 2011/11/04 · openalex publication_date 2011/11/04 · arxiv updated 2015/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

I will discuss the recent proof that the complexity class NEXP (nondeterministic exponential time) lacks nonuniform ACC circuits of polynomial size. The proof will be described from the perspective of someone trying to discover it.

Citations

• Which Problems Have Strongly Exponential Complexity?
• 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General

Related

• On the Consistency of Circuit Lower Bounds for Non-Deterministic Time
• On the Incompressibility of Truth With Application to Circuit Complexity
• Symmetric Exponential Time Requires Near-Maximum Circuit Size
• A Note on Nonuniform versus Uniform ACC^k Circuits for NE
• Relationship between circuit complexity and symmetry