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 »Razborov: On the minimal density of triangles in graphs, Combinatorics, Probability and Computing} 17(4):603-618, 2008..
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
Catégorie:Naissance en février 1963 Catégorie:Mathématicien soviétique Catégorie:Personnalité en informatique théorique Catégorie:Étudiant de l'université d'État de Moscou Catégorie:Professeur à l'université de Chicago Catégorie:Lauréat du prix Gödel Catégorie:Lauréat du prix Nevanlinna Catégorie:Gödel Lecturer Catégorie:Tarski Lecturer Catégorie:Lauréat du prix Robbins Catégorie:Membre de l'Académie des sciences de Russie Catégorie:Participant aux Olympiades internationales de mathématiques Catégorie:Mathématicien russe du XXe siècle Catégorie:Mathématicien russe du XXIe siècle