Thinking Algorithmically About Impossibility

11 Dec
Monday, 12/11/2017 4:00pm to 5:00pm
Computer Science Building, Room 142
Theory Seminar

Distinguished Theory Seminar

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).

Faculty Host