*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Alexander Razborov
Steklov Mathematical Institute and IAS
"Grand Challenges in Complexity Theory"
Abstract: 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.
Bio: 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 faculty of the Steklov Mathematical Institute in 1989 and have been working there since that. In 1999-2000 he was a Visiting
Researcher at the Department of Computer Science of Princeton University, and in 2000-2008 he is holding a visiting position at the Institute for Advanced Study, Princeton.
During his career, Professor Razborov worked in various areas including mathematical logic, computational complexity, proof complexity and
combinatorics. Among other things, his contributions include:
Professor Razborov is a member of Academia Europea (since 1993), and a corresponding member of the Russian Academy of Sciences (since 2000). He is a recipient of the Nevanlinna prize awarded by the International Mathematical Union (1990) and of the Goedel Prize (awarded jointly by EATCS and ACM, 2007).
