Quick links

Grand Challenges in Complexity Theory

Date and Time
Thursday, October 25, 2007 - 4:30pm to 6:00pm
Computer Science Small Auditorium (Room 105)
Alexander Razborov, from IAS
Bernard Chazelle
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.

Follow us: Facebook Twitter Linkedin