Joint Colloquium Distinguished Lecture Series

Grand Challenges in Complexity Theory

This event is co-sponsored by the Department of Mathematics

photo of Alexander Razborov Wednesday, October 31, 2007
306 Soda Hall (HP Auditorium)
4:00 - 5:00 pm

Alexander Razborov
Institute for Advanced Study


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.


Professor Alexander A. Razborov graduated from the Moscow State University (department for mathematics and mechanics) in 1985 and in the same year entered the graduate school of the Steklov Mathematical Institute of the Russian Academy of Sciences. He defended his PhD thesis ("On systems of equations in free groups") in 1987, and his doctoral thesis ("Lower Bounds in the Boolean Complexity") in 1991. Professor Razborov joined the faculty of the Steklov Mathematical Institute in 1989. In 1999-2000 he was a Visiting Researcher at the Department of Computer Science of Princeton University, and since 2000 he has held a visiting position at the Institute for Advanced Study, Princeton. During his career, Professor Razborov has worked in various areas including mathematical logic, computational complexity, proof complexity and combinatorics. He was awarded the Nevanlinna Prize in 1990 and the Godel Prize (jointly with Steven Rudich) in 2007.

  Return to EECS Joint Colloquium