Open Lecture — Thinking Algorithmically About Impossibility

Complexity lower bounds like P != NP assert that no efficient program exists for solving many important computational problems. The stability of modern commerce relies on certain lower bounds being true (most prominently in cryptography and computer security). But the general problem of mathematically proving computational lower bounds remains a mystery: for many of the prominent lower bound problems, we do not know how to begin proving them true. While computer science is extremely adept at designing algorithms, it still seems very difficult to reason about all possible algorithms, including those that we will never see or execute, and argue that none of them can solve an NP-complete problem.

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 will argue that some progress can be made by (very deliberately) thinking *algorithmically* about lower bounds: looking at lower bound problems as algorithm design problems of a different form. Recently, several new approaches have been proposed for viewing lower bounds in this way. This talk will provide a gentle introduction to these new approaches, and the general philosophy behind them.

Light refreshments will be served before the lecture at 3:30 p.m.