Alexander Alexandrovich Razborov

from Wikipedia, the free encyclopedia

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

Rasborow studied 1980 to 1985 at the Lomonossow University (Faculty of Mathematics and Mechanics) and after graduating from 1985 to 1987 with Sergei Adjan at the Steklow Institute , where he received his doctorate in 1987 ( On systems of equations in free groups ). He then worked as a researcher at the Steklow Institute, from 1991 as head of a working group (Leading Researcher) and from 2008 with the title of Principal Researcher . In 1991 he received the Russian doctorate degree ( Lower Limits in Boolean Complexity ). Since 2008 he has been the Andrew McLeish Distinguished Service Professor in the Department of Computer Science at the University of Chicago . From 1999 to 2000 he was visiting scholar at Princeton University and from 1993 to 1994 and 2000 to 2008 he was at the Institute for Advanced Study (2003 to 2008 as visiting professor). He is also part-time (2012) at the Steklow Institute and the Toyota Technological Institute in Chicago.

In 1990 he was awarded the Nevanlinna Prize for his method of lower limits for the circuit complexity to find (Boolean Circuit Complexity). He showed that the gap in circuit complexity between monotonic Boolean functions (those made up of logical and, or and identity, not with negation) and non-monotonic super-polynomial ( improved to exponential by Noga Alon / RB Boppana and Éva Tardos ).

In 2007 he and Steven Rudich received the Gödel Prize for their work Natural Proof , which showed that circuit complexity methods for determining a lower limit of the complexity of a problem are probably not suitable for solving the P-NP problem . In doing so, they isolated a common characteristic of these circuit complexity methods, which they call Natural Proof . They showed that a natural proof for the P = NP problem would result in no pseudo-random number generators, which is generally accepted. They further showed that there is no natural proof evidence that some 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 one had to look in new directions for the solution.

In extremal graph theory, he achieved partial results in the clique density problem by László Lovász and Miklós Simonovits (generally solved in 2016 by Christian Reiher ).

Since 2000 he has been a corresponding member of the Russian Academy of Sciences . In 2000 he gave the Tarski Lectures . Since 1993 he has been a member of the Academia Europaea . In 1998 he gave the Paul Erdős Lectures in Jerusalem and the Coxeter Lectures at the Fields Institute in Toronto. In 1986 he was invited speaker at the ICM in Berkeley ( Lower bounds for monotone complexity of boolean functions ). In 2010 he was a Gödel lecturer .

In 2013 he was awarded the American Mathematical Society's David P. Robbins Prize for his work On the minimal density of triangles in graphs and for introducing flag algebras as a powerful new method in extremal combinatorics. Rasborow thus solved an old long open problem of extreme combinatorics, the question of the minimum number of triangles in graphs with n vertices and m edges.

In 2020 Razborov was elected to the American Academy of Arts and Sciences .

Fonts (selection)

Except for the works cited in the footnotes:

  • A lower bound on the monotone network complexity of the logical permanent , Math. Notes Acad. Sci. USSR, Vol. 37, 1985, pp. 485-493
  • On the method of approximation , Proc. 21. STOC (ACM Symposium on the Theory of Computing), 1989, pp. 167-176
  • The P = NP problem, a view from the 1990s. In: Bolibruch, Osipov, Sinai (Ed.): Mathematical Events of the Twentieth Century. Springer 2006, p. 331.
  • Flag algebras. J. Symbolic Logic, Vol. 72, 2007, pp. 1239-1282.

Web links

Individual evidence

  1. ^ Razborov: Lower bounds for the monotone complexity of some Boolean functions. Soviet Math. Doklady, Vol. 31, 1985, p. 354 (PDF; 482 kB).
  2. ↑ Noga Alon, RB Boppana, The monotone circuit complexity of Boolean functions, Combinatorica, Volume 7, 1987, pp 1-22
  3. ^ Razborov, Rudich: Natural Proof. Journal of Computer and System Sciences, Vol. 55, 1997, pp. 24-35 and Proc. 26th Int. ACM Symposium on the Theory of Computing (STOC), 1994, p. 204, online , Postscript file.
  4. ^ Combinatorics, Probability and Computing. Volume 17, 2008, pp. 603-618.
  5. ^ David P. Robbins Prize.
personal data
SURNAME Razborov, Alexander Alexandrovich
ALTERNATIVE NAMES Razborov, Alexander; Разборов, Александр Александрович (Russian spelling)
BRIEF DESCRIPTION Russian mathematician
DATE OF BIRTH February 6, 1963
PLACE OF BIRTH Belowo