Thinking Algorithmically About Impossibility (Invited Talk)

Complexity lower bounds like P! = NP assert impossibility results for all possible programs of some restricted form. As there are presently enormous gaps in our lower bound knowledge, a central question on the minds of today's complexity theorists is how will we find better ways to reason about all efficient programs? I argue that some progress can be made by (very deliberately) thinking algorithmically about lower bounds. Slightly more precisely, to prove a lower bound against some class C of programs, we can start by treating C as a set of inputs to another (larger) process, which is intended to perform some basic analysis of programs in C. By carefully studying the algorithmic "meta-analysis" of programs in C, we can learn more about the limitations of the programs being analyzed. This essay is mostly self-contained; scant knowledge is assumed of the reader.

Authors

• R. Ryan Williams

Keywords

• satisfiability
• derandomization
• circuit complexity