Alexander Razborov

gives a talk on

Proof Complexity of Pigeonhole Principles  (abstract

(June 13, 2002,  16 Uhr c.t. Magnus-Hoersaal, Robert Mayer Strasse 11-15)


Alexander Alexandrovich Razborov (aka Sasha Razborov) is widely recognized as a leading figure in mathematics and computer science.
His work presenting superpolynomial lower bounds on the size required to compute certain functions on monotone
or constant-depth circuits has had a profound influence on recent progress in complexity theory; for this work he was
awarded the Nevanlinna prize of the International Mathematical Union in 1990.

The Work of A.A. Razborov, a talk given by László Lovász  (right in the picture) at International Congress of Mathematicians (1990)

Sasha did his undergraduate work at Moscow University, in the Department of Mechanics and Mathematics.
While there, he studied combinatorial group theory under S. I. Adian. He completed his undergraduate studies in 1985
and in the same year became a graduate student at the Steklov Mathematical Institute, Moscow. In 1987 he finished this
course, defended his PhD thesis ("On systems of equations in free groups") and was hired to the Steklov
Mathematical Institute. In 1991 he defended his doctoral thesis ("Lower Bounds in the Boolean Complexity").

In 1993 he was elected to the Academia Europea.

At present he is at the University of Chicago (USA).

Added later: Sasha also won the Gödel Prize with Steven Rudich in 2007 for their paper "Natural Proofs".