10-25

Grand Challenges in Complexity Theory

Modern complexity theory is a vast, loosely defined area. Its methods and methodology can be successfully applied whenever one has a set of tasks, a class of admissible solutions, and numerical characteristics to measure the ``quality'' of a solution. This talk will focus on two specific scenarios: classical computational complexity and proof complexity.

The story I will tell, however, is highly representative of the methods that have been tried in the field at large, with its mixed bag of successes, setbacks, and promising directions.

I will try to reveal some of the tight, beautiful and unexpected connections existing between different branches of complexity theory. I will discuss the ``grand challenges'' of the field, including "P vs NP" and questions about the power of classical proof systems.

This talk will assume no prior knowledge in theoretical computer science.