Accueil🇫🇷Chercher

László Babai

László Babai ([ˈlaːsloː], [ˈbɒbɒi]), né le à 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.

László Babai
Description de cette image, également commentée ci-après
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

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 fondamental en théorie de la complexité NP. Ce résultat émerveille la communauté scientifique de l'algorithmique[2].

Références

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.