Alexander Razborov

Alexander Alexandrovich Rasborow (Russian Александр Александрович Разборов, English transliteration Alexander Razborov, born February 6, 1963 in Belovo ) is a Russian computer scientist and mathematician.

Rasborow studied from 1980 to 1985 at the Moscow State University (Faculty of Mathematics and Mechanics ) and after graduating from 1985 to 1987 when Sergei Adian at the Steklov Institute, in which he. Received his doctorate in 1987 ( using systems of equations in free groups ) After that, he was a researcher at the Steklov Institute, from 1991 as head of a working group (Leading Researcher ) and from 2008 entitled Principal Researcher. In 1991 he received the Russian doctoral degree ( Lower bounds in Boolean complexity). Since 2008 he has Andrew McLeish Distinguished Service Professor in the Faculty of computer science at the University of Chicago. 1999 to 2000 he was a visiting scholar at Princeton University and from 1993 to 1994 and 2000 to 2008 he was at the Institute for Advanced Study ( 2003-2008 as a visiting professor ). In part time, he is also (2012 ) nor the Steklov Institute and at the Toyota Technological Institute in Chicago.

In 1990 he was awarded the Nevanlinna Prize for his method of finding lower bounds for the circuit complexity (Boolean Circuit Complexity ).

In 2007 he was awarded with Steven Rudich the Gödel Prize for their work Natural Proof, which showed that circuit complexity methods are probably not suitable for the determination of a lower limit to the complexity of a problem, to solve the P- NP problem .. They isolated a common property this circuit complexity method, which they call Natural proof. They showed that a natural proof- proof of P = NP problem would have the consequence that no pseudo-random generators exist, but what is generally believed. Next, they showed that there is no natural proof evidence that some well-known cryptographic problems are NP-hard (such as the factorization of integers or the discrete logarithm problem ). The work of Razborov and Rudich was an important advance in the P = NP problem, one of the Clay problems, which showed that you had to look in new directions for the solution.

Since 2000 he is a corresponding member of the Russian Academy of Sciences. In 2000 he held the Tarski Lectures. Since 1993 he is member of the Academia Europaea. In 1998 he held the Paul Erdos Lectures in Jerusalem and the Coxeter Lectures at the Fields Institute in Toronto. In 1986 he was invited speaker at the ICM, Berkeley ( Lower bounds for monotone complexity of boolean functions). In 2010 he was Lecturer Godel.

In 2013 he received the David P. Robbins Prize from the American Mathematical Society for his work On the minimal density of triangles in graphs and the introduction of flag algebras (Flag Algebras ) as a powerful new method in extremal combinatorics. Rasborow thus replaces an old long open problem of extremal combinatorics, the question of the minimum number of triangles in graphs with n vertices and m edges.

Writings

• The P = NP Problem, a view from the 1990s, in Bolibruch, Osipov, Sinai (Editor) Mathematical Events of the Twentieth Century, Springer 2006, pp. 331
• Flag Algebras, J. Symbolic Logic, Volume 72, 2007, pp. 1239-1282