László Babai (, ), né le à Budapest, est un professeur de mathématiques et d'informatique hongro-américain, enseignant actuellement à l'université de Chicago. Il est connu pour les systèmes de preuve interactive, l'introduction du terme « algorithme de Las Vegas » et l'utilisation de méthodes de la théorie des groupes pour le problème de l'isomorphisme de graphes. Il est lauréat du prix Gödel 1993.
En il proposeLászló Babai Graph Isomorphism in Quasipolynomial Time sur ArXiV.org. un algorithme quasi-polynomial pour résoudre le problème de l'isomorphisme de graphes, faisant largement descendre la borne de complexité de ce problème qui joue un rôle déterminant en théorie de la complexité NP. Ce résultat émerveille la communauté scientifique de l'algorithmiqueQuantum magazine Landmark Algorithm Breaks 30-Year Impasse.
Travaux
Distinctions Médaille Tibor-Szele (1993)
Références
Liens externes
Catégorie:Mathématicien hongrois du XXe siècle Catégorie:Mathématicien hongrois du XXIe siècle Catégorie:Personnalité hongroise de l'informatique Catégorie:Personnalité en combinatoire Catégorie:Universitaire hongrois Catégorie:Étudiant de l'université Loránd-Eötvös Catégorie:Professeur à l'université de Chicago Catégorie:Lauréat du prix Gödel Catégorie:Membre de l'Académie hongroise des sciences Catégorie:Membre de l'Académie américaine des arts et des sciences Catégorie:Participant aux Olympiades internationales de mathématiques Catégorie:Naissance à Budapest Catégorie:Naissance en juillet 1950 Catégorie:Lauréat du prix Knuth