Alexandre Razborov

Alexandre Alexandrovitch Razborov (russe : Алекса́ндр Алекса́ндрович Разбо́ров, 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é[1], et en 2007 du prix Gödel avec Steven Rudich pour leur article « Natural proofs »[2].

Alexander Razborov
Naissance
Nationalité Russie
Résidence États-Unis
Domaines Informatique théorique, mathématiques
Institutions Institut de mathématiques Steklov, Université de Chicago, Toyota Technological Institute at Chicago (en)
Diplôme Université d'État de Moscou
Renommé pour théorie des groupes, informatique théorique
Distinctions Prix Nevanlinna (1990)
Prix Gödel (2007)
Site people.cs.uchicago.edu/~razborov

Biographie

Son directeur de thèse est Sergueï Adian[3]. Razborov devient en 2009 Andrew MacLeish (en) 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[4]. Son nombre d'Erdős est 2[5]. 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 »[6].

Travaux

Son travail le plus connu, en collaboration avec Steven Rudich, est l'introduction de la notion de preuve naturelle (natural proofs), 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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Alexander Razborov » (voir la liste des auteurs).

Voir aussi

Articles connexes

Liens externes

  • Portail des mathématiques
  • Portail de la Russie
  • Portail de l’URSS
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.