Alexandre Razborov

Alexander Razborov

Données clés
Naissance (61 ans)
Nationalité Drapeau de la Russie Russie
Résidence Drapeau des États-Unis États-Unis
Données clés
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

modifier Consultez la documentation du modèle

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].

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

  • (en) « Lower bounds for the monotone complexity of some Boolean functions », Doklady Akademii Nauk SSSR, vol. 31,‎ , p. 354–357 (lire en ligne [pdf])
  • (en) « Lower bounds on monotone complexity of the logical permanent », Mathematical Notes of the Academy of Sciences of the USSR, vol. 37, no 6,‎ , p. 485–493 (DOI 10.1007/BF01157687)
  • (ru) О системах уравнений в свободной группе, Московский государственный университет,‎ (lire en ligne) (PhD thesis. 32.56MB)
  • (en) « Lower bounds on the size of bounded depth circuits over a complete basis with logical addition », Mathematical Notes of the Academy of Sciences of the USSR, vol. 41, no 4,‎ , p. 333–338 (DOI 10.1007/BF01137685)
  • (en) « On the method of approximations », dans Proceedings of the 21st Annual ACM Symposium on the Theory of Computing, Seattle, Washington, USA, , 167–176 p. (DOI 10.1145/73007.73023, lire en ligne [pdf. 1.41MB])
  • (en) « Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits », Mathematical Notes of the Academy of Sciences of the USSR, vol. 48, no 6,‎ , p. 1226–1234 (DOI 10.1007/BF01240265)
  • (en) (avec Stephen Rudich), « Natural proofs », dans Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, Montréal, Québec, Canada, , 204–213 p., PostScript (DOI 10.1145/195058.195134, lire en ligne)
  • (en) « Lower Bounds for the Polynomial Calculus », Computational Complexity, vol. 7, no 4,‎ , p. 291–324 (DOI 10.1007/s000370050013, lire en ligne [ps])
  • (en) « Propositional proof complexity », Journal of the ACM, vol. 50, no 1,‎ , p. 80–82 (DOI 10.1145/602382.602406, lire en ligne [ps]) (Survey paper for JACM's 50th anniversary)

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).
  1. ↑ (en) « International Mathematical Union: Rolf Nevanlinna Prize Winners » [archive du ] (consulté le )
  2. ↑ (en) « EATCS: Gödel Prize - 2007 »
  3. ↑ (en) « Alexandre Razborov », sur le site du Mathematics Genealogy Project
  4. ↑ (en) « Russian Academy of Sciences: Razborov Aleksandr Aleksandrovich: General info: History »
  5. ↑ (en) « Some Famous People with Finite Erdös Numbers : Nevanlinna Prize winners »
  6. ↑ Razborov: On the minimal density of triangles in graphs, Combinatorics, Probability and Computing} 17(4):603-618, 2008.

Voir aussi

Articles connexes

Liens externes

  • Notices d'autoritéVoir et modifier les données sur Wikidata :
    • VIAF
    • NUKAT
  • Ressources relatives à la rechercheVoir et modifier les données sur Wikidata :
    • Digital Bibliography & Library Project
    • Mathematics Genealogy Project
    • Scopus
  • (en) Alexander Razborov's Home Page
  • (en) All-Russian Mathematical Portal: Persons: Razborov Alexander Alexandrovich
  • (en) Biography sketch in the Toyota Technological Institute at Chicago.
  • (en) Curricula Vitae at the Department of Computer Science, University of Chicago
  • (en) DBLP: Alexander A. Razborov
  • (en) "Items authored by Razborov, A. A." (MathSciNet, accès restreint)
  • (en) The Work of A.A. Razborov – un article de László Lovász dans les Proceedings of the ICM, Kyōto, Japon, 1990
v · m
Lauréats du prix Nevanlinna
v · m
Lauréats du prix Gödel
  • icône décorative Portail des mathématiques
  • icône décorative Portail de la Russie
  • icône décorative Portail de l’URSS
  • icône décorative Portail de l'informatique théorique