László Babai
László Babai
László Babai
| Naissance |
Budapest (Hongrie) |
|---|---|
| Nationalité | Hongrois |
| 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 à 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 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 déterminant en théorie de la complexité NP. Ce résultat émerveille la communauté scientifique de l'algorithmique[2].
Travaux
Distinctions
- Médaille Tibor-Szele (1993)
Références
Liens externes
- Site officiel
- Ressources relatives à la recherche :
- Portail des mathématiques
- Portail de la Hongrie
- Portail de l'informatique théorique