Alexander Razborov

Alexander Razborov
Naissance	16 février 1963
Domicile	États-Unis
Nationalité	Russie
Champs	Informatique théorique, mathématiques
Institution	Institut de mathématiques Steklov, Université de Chicago, Toyota Technological Institute at Chicago (en)
Diplômé de	Université d'État de Moscou
Renommé pour	théorie des groupes, informatique théorique
Distinctions	Prix Nevanlinna (1990) Prix Gödel (2007)
modifier

Aleksandr Aleksandrovich Razborov (russe : Алекса́ндр Алекса́ндрович Разбо́ров, né le 16 février 1963), connu aussi sous le nom de Sasha 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 (en) pour leur article « Natural proofs (en) »^[2].

Son directeur de thèse est Sergei Adian (en). Il est élu le 26 mai 2000 membre correspondant de l'Académie des sciences de Russie^[3]. Son nombre d'Erdős est 2^[4].

Son travail le plus connu, en collaboration avec Steven Rudich, est l'introduction de la notion de 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.

Razborov devient en 2009 le Andrew MacLeish (en) Distinguished Service Professor dans le département informatique de l'université de Chicago.

Bibliographie

• (en) « Lower bounds for the monotone complexity of some Boolean functions », dans Soviet Mathematics Doklady, vol. 31, 1985, p. 354–357 [texte intégral [pdf]] 
• (en) « Lower bounds on monotone complexity of the logical permanent », dans Mathematical Notes of the Academy of Sciences of the USSR, vol. 37, n^o 6, juin 1985, p. 485–493 [lien DOI] 
• (ru) О системах уравнений в свободной группе, Московский государственный университет, 1987 [lire en ligne]  (PhD thesis. 32.56MB)
• (en) « Lower bounds on the size of bounded depth circuits over a complete basis with logical addition », dans Mathematical Notes of the Academy of Sciences of the USSR, vol. 41, n^o 4, avril 1987, p. 333–338 [lien DOI] 
• (en) « On the method of approximations », dans Proceedings of the 21st Annual ACM Symposium on the Theory of Computing, Seattle, Washington, USA, mai 1989, pdf. 1.41MB, 167–176 p. [lire en ligne] 
• (en) « Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits », dans Mathematical Notes of the Academy of Sciences of the USSR, vol. 48, n^o 6, décembre 1990, p. 1226–1234 [lien DOI] 
• (en) (avec Stephen Rudich), « Natural proofs », dans Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, Montréal, Québec, Canada, mai 1994, PostScript, 204–213 p. [lire en ligne] 
• (en) « Lower Bounds for the Polynomial Calculus », dans Computational Complexity, vol. 7, n^o 4, décembre 1998, p. 291–324 [texte intégral [ps], lien DOI] 
• (en) « Propositional proof complexity », dans Journal of the ACM (en), vol. 50, n^o 1, janvier 2003, p. 80–82 [texte intégral (ps), lien DOI]  (Survey paper for JACM's 50th anniversary)

Notes et références

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

Voir aussi

Articles connexes

• Avi Wigderson
• Groupe libre
• Règle de résolution

Liens externes

• (en) Alexander Razborov sur le site du Mathematics Genealogy Project
• (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

• Portail de l’informatique
• Portail des mathématiques
• Portail de la Russie
• Portail de l’URSS