László Babai

Cet article est une ébauche concernant une personnalité hongroise.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

László Babai

László Babai

Données clés
Naissance	20 juillet 1950 (73 ans) Budapest (Hongrie)
Nationalité	Hongrois

Données clés
Domaines	Mathématiques
Institutions	Université de Chicago
Diplôme	Université Loránd Eötvös
Directeur de thèse	Pál Turán Vera Sós
Étudiants en thèse	Mario Szegedy
Site	people.cs.uchicago.edu/~laci

László Babai ([ˈlaːsloː], [ˈbɒbɒi]), né le 20 juillet 1950 à Budapest, est un professeur de mathématiques et d'informatique hongrois, 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 décembre 2015 il propose^[1] 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 fondamental en théorie de la complexité NP. Ce résultat émerveille la communauté scientifique de l'algorithmique^[2].

Travaux[modifier | modifier le code]

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Distinctions[modifier | modifier le code]

Médaille Tibor-Szele (1993)

Références[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Notices d'autorité :
- VIAF
- ISNI
- GND
- Israël
- WorldCat
Ressources relatives à la recherche :
Page personnelle sur le site de l'université de Chicago

[1] László Babai Graph Isomorphism in Quasipolynomial Time sur ArXiV.org.

[2] Quantum magazine Landmark Algorithm Breaks 30-Year Impasse

[1]

[2]