December 11, 2017 Distinguished Theory Seminar 4:00 pm, CS 142

Thinking Algorithmically About Impossibility

Ryan Williams
MIT

Abstract: There are presently enormous gaps in our knowledge about computational lower bounds, and there are barrier results indicating that the usual methods of reasoning won't suffice to prove strong lower bounds. So 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: viewing lower bound problems as algorithm design problems of a different form, and solving these algorithmic problems. Recently, several new approaches have been proposed for viewing lower bounds in this way. I will give an overview of some of these methods (focusing on those that I personally know best).