László "Laci" Babai (nacido el 20 de julio de 1950 en Budapest ) [1] es un profesor húngaro de informática y matemáticas en la Universidad de Chicago . Su investigación se centra en la teoría de la complejidad computacional , los algoritmos , la combinatoria y los grupos finitos , con énfasis en las interacciones entre estos campos.
En 1968, Babai ganó una medalla de oro en la Olimpiada Internacional de Matemáticas . Babai estudió matemáticas en la Facultad de Ciencias de la Universidad Eötvös Loránd de 1968 a 1973, recibió un doctorado de la Academia Húngara de Ciencias en 1975 y recibió un DSc de la Academia Húngara de Ciencias en 1984. [1] [2] Ocupó un puesto de profesor en la Universidad Eötvös Loránd desde 1971; en 1987 asumió puestos conjuntos como profesor de álgebra en Eötvös Loránd y de informática en la Universidad de Chicago. En 1995, comenzó un nombramiento conjunto en el departamento de matemáticas de Chicago y renunció a su puesto en Eötvös Loránd. [1]
Es autor de más de 180 artículos académicos. [1] Sus logros notables incluyen la introducción de sistemas de prueba interactivos , [3] la introducción del término algoritmo de Las Vegas , [4] y la introducción de métodos teóricos de grupo en pruebas de isomorfismo de grafos . [4] En noviembre de 2015, anunció un algoritmo de tiempo cuasipolinomial para el problema de isomorfismo de grafos . [5] [6]
Es editor en jefe de la revista en línea arbitrada Theory of Computing . [7] Babai también participó en la creación del programa Semestres de Budapest en Matemáticas y fue el primero en acuñar el nombre.
Después de anunciar el resultado en 2015, [6] [8] [9] Babai presentó un artículo que demostraba que el problema del isomorfismo de grafos se puede resolver en tiempo cuasi-polinomial en 2016, en el Simposio ACM sobre Teoría de la Computación . [10] En respuesta a un error descubierto por Harald Helfgott , publicó una actualización en 2017. [11]
Mostramos que el problema del isomorfismo de grafos (GI) y los problemas relacionados del isomorfismo de cuerdas [12] (bajo acción de grupo) (SI) y la intersección de cosets (CI) [13] [14] se pueden resolver en tiempo cuasipolinomial. El mejor límite previo para GI era donde es el número de vértices ( Luks , 1983); para los otros dos problemas, el límite era similar, donde es el tamaño del dominio de permutación (Babai, 1983). El algoritmo se basa en el marco SI de Luks y ataca las configuraciones de barrera para el algoritmo de Luks mediante «certificados locales» teóricos de grupos y técnicas de partición canónica combinatoria. Mostramos que en un sentido bien definido, los grafos de Johnson son las únicas obstrucciones para la partición canónica efectiva.
En 1988, Babai ganó el Premio Estatal Húngaro, en 1990 fue elegido miembro correspondiente de la Academia Húngara de Ciencias y en 1994 se convirtió en miembro de pleno derecho. [1] En 1999, la Universidad de Tecnología y Economía de Budapest le otorgó un doctorado honorario. [1]
En 1993, Babai recibió el Premio Gödel junto con Shafi Goldwasser , Silvio Micali , Shlomo Moran y Charles Rackoff , por sus artículos sobre sistemas de prueba interactivos. [15]
En 2015, fue elegido [16] miembro de la Academia Estadounidense de las Artes y las Ciencias y ganó el Premio Knuth .
Babai fue orador invitado en los Congresos Internacionales de Matemáticos en Kioto (1990), Zúrich (1994, charla plenaria) y Río de Janeiro (2018).
