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:

1. The first description of solutions of equations in a free group.
2. Solving the analogue of the P vs. NP question for a number
3. of restricted models of computation.
4. Theory of Natural Proofs and closely related theory of feasible provability of major open problems in Complexity Theory, accompanied by many concrete lower bounds for the corresponding proof systems.
5. Lower bounds in quantum communication complexity.
6. The theory of Flag Algebras in Extremal Combinatorics.

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).