Quebec Mathematical Sciences Colloquium

October 15, 2010 from 16:00 to 18:00 (Montreal/Miami time) On location

Grand Challenges in Complexity Theory

Colloquium presented by Alexander Razborov

Conférence s'adressant à un large auditoire / Suitable for a general audience 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 we 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.

Address

CRM, UdeM, Pavillon André-Aisenstadt, 2920, chemin de la tour, room 1360