A Casual Tour Around a Circuit Complexity Bound

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.

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

References in corpus (2)

• 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
• A Satisfiability Algorithm for AC${}^0$

Cited by in corpus (1)

• Fine-grained quantum computational supremacy