Alexandre Razborov
Alexandre Alexandrovitch Razborov (, né le ), connu aussi sous le nom de Sacha Razborov, est un mathématicien et un informaticien théoricien soviétique et russe. Il est le lauréat du prix Nevanlinna en 1990 pour son travail sur la théorie de la complexité, et en 2007 du prix Gödel avec Steven Rudich pour leur article « Natural proofs ».

Biographie 

Son directeur de thèse est Sergueï Adian.
Razborov devient en 2009  Distinguished Service Professor au département informatique de l'université de Chicago.

Prix et distinctions 
Il est élu le  membre correspondant de l'Académie des sciences de Russie.
Son nombre d'Erdős est 2.
En 2010 il est Gödel Lecturer avec une conférence intitulée Complexity of Propositional Proofs.
En 2013, il reçoit le prix Robbins pour son article « On the minimal density of triangles in graphs ».

Travaux 

Son travail le plus connu, en collaboration avec Steven Rudich, est l'introduction de la notion de preuve naturelle (), une classe de stratégies permettant de prouver des bornes inférieures dans la théorie de la complexité des algorithmes. En particulier Razborov et Rudich ont montré que sous l'hypothèse que certaines fonctions à sens unique existent, de telles preuves ne permettent pas de résoudre le problème P = NP, qui nécessiterait alors de nouvelles techniques.

Bibliographie

Notes et références

Voir aussi

Articles connexes 
 Avi Wigderson
 Groupe libre
 Règle de résolution

Liens externes 
 
 
  Alexander Razborov's Home Page
  All-Russian Mathematical Portal: Persons: Razborov Alexander Alexandrovich
  Biography sketch in the Toyota Technological Institute at Chicago.
  Curricula Vitae at the Department of Computer Science, University of Chicago
  DBLP: Alexander A. Razborov
  "Items authored by Razborov, A. A." (MathSciNet, accès restreint)
  The Work of A.A. Razborov – un article de László Lovász dans les Proceedings of the ICM, Kyōto, Japon, 1990

Naissance en février 1963
Mathématicien soviétique
Personnalité en informatique théorique
Étudiant de l'université d'État de Moscou
Professeur à l'université de Chicago
Lauréat du prix Gödel
Lauréat du prix Nevanlinna
Gödel Lecturer
Tarski Lecturer
Lauréat du prix Robbins
Membre de l'Académie des sciences de Russie
Participant aux Olympiades internationales de mathématiques
Mathématicien russe du XXe siècle
Mathématicien russe du XXIe siècle