Valentine Kabanets
(Simon Fraser University)
Meta-Algorithms versus Circuit Lower Bounds

Algorithms and lower bounds play complementary roles in computer science. Both contribute to better understanding of what is and is not efficiently computable, the fundamental question in computational complexity, but approach this question from the opposite sides.

In this talk, I will argue that there is deep connection between algorithms (for certain "general enough" computational problems) and lower bounds (for related problems). Such a connection has been discovered in a number of cases already, and was used to advance both the discovery of new algorithms and the proofs of new lower bounds. I will discuss a few such important examples, and suggest directions for further exploration of this intriguing connection.