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.
László Babai | |
---|---|
Nació | |
Nacionalidad | húngaro |
alma mater | Academia de Ciencias de Hungría |
Premios | Premio Gödel (1993) Premio Knuth (2015) Premio Dijkstra (2016) |
Carrera científica | |
Campos | Ciencias de la Computación , Matemáticas |
Instituciones | Universidad de Chicago |
Asesor de doctorado | Pál Turán Vera T. Sós |
Estudiantes de doctorado | Mario Szegedy Gábor Tardos |
La vida
En 1968, Babai ganó una medalla de oro en la Olimpiada Internacional de Matemáticas . Babai estudió matemáticas en la Universidad Eötvös Loránd de 1968 a 1973, recibió un doctorado. de la Academia de Ciencias de Hungría en 1975, y recibió un D.Sc. de la Academia de Ciencias de Hungría en 1984. [1] [2] Ocupó un puesto de profesor en la Universidad Eötvös Loránd desde 1971; en 1987 ocupó cargos 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 dejó su puesto en Eötvös Loránd. [1]
Trabaja
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 las 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 de referencia Theory of Computing . [7] Babai también participó en la creación del programa Semestres de Matemáticas de Budapest y fue el primero en acuñar el nombre.
Graficar isomorfismo en tiempo cuasipolinomial
Después de anunciar el resultado en 2015, [6] [8] [9] Babai presentó un artículo que demuestra que el problema del isomorfismo gráfico 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].
Demostramos que el problema de Graph Isomorphism (GI) y los problemas relacionados de String Isomorphism [12] (bajo acción de grupo) (SI) y Coset Intersection (CI) [13] [14] se pueden resolver en cuasipolynomialhora. El mejor destino anterior para GI fue dónde es el número de vértices ( Luks , 1983); para los otros dos problemas, el límite era similar, dónde 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 grupo y técnicas de partición canónica combinatoria. Mostramos que, en un sentido bien definido, las gráficas de Johnson son las únicas obstrucciones para una partición canónica efectiva.
Honores
En 1988, Babai ganó el Premio Estatal de Hungría, en 1990 fue elegido miembro correspondiente de la Academia de Ciencias de Hungría 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 honoris causa. [1]
En 1993, Babai recibió el Premio Gödel junto con Shafi Goldwasser , Silvio Micali , Shlomo Moran y Charles Rackoff , por sus trabajos sobre sistemas de prueba interactivos. [15]
En 2015, fue elegido [16] miembro de la Academia Estadounidense de Artes y 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).
Fuentes
- El algoritmo del profesor László Babai es el siguiente gran paso para conquistar el isomorfismo en los gráficos // Publicado el 20 de noviembre de 2015 División de Ciencias Físicas / Universidad de Chicago
- Matemático afirma un gran avance en la teoría de la complejidad , por Adrian Cho 10 de noviembre de 2015 17:45 // Publicado en Ciencias, Matemáticas Noticias AAAS
- Un algoritmo de tiempo cuasipolinomial para el isomorfismo de gráficos: los detalles + los antecedentes del isomorfismo de los gráficos + el resultado principal // Matemáticas ∩ Programación. Publicado el 12 de noviembre de 2015 por j2kun
- El algoritmo histórico rompe el callejón sin salida de 30 años , el algoritmo resuelve el isomorfismo gráfico en un tiempo récord // Revista Quanta. Por: Erica Klarreich, 14 de diciembre de 2015
- Un poco más sobre el algoritmo de isomorfismo gráfico // 21 de noviembre de 2015, por RJLipton + KWRegan (Ken Regan y Dick Lipton)
- [Ласло] Бабай приблизился к решению «проблемы тысячелетия» // Наука Lenta.ru, 14:48, 20 de enero de 2015
- copia de Lenta.ru // texnomaniya.ru, 20 de ноября 2015
- Опубликован быстрый алгоритм для задачи изоморфизма графов // Анатолий Ализар, Хабрахабр, 16 декабря в 02:12ря в
- Опубліковано швидкий алгоритм для задачі ізоморфізму графів // Джерело: Хабрахабр, перекладкий, перекладеня 16 de marzo de 2015, 06:30
Referencias
- ^ a b c d e f Curriculum vitae del sitio web de Babai, consultado el 28 de enero de 2016.
- ^ László Babai en el Proyecto de genealogía matemática
- ^ Babai, László; Moran, Shlomo (1988), "Juegos de Arthur-Merlin: un sistema de prueba aleatorio y una jerarquía de clases de complejidad", J. Comput. Syst. Sci. , 36 (2): 254–276, doi : 10.1016 / 0022-0000 (88) 90028-1.
- ^ a b Babai, László (1979), algoritmos de Monte-Carlo en pruebas de isomorfismo de grafos (PDF) , Tech. Informe, Université de Montréal.
- ^ Cho, Adrian (10 de noviembre de 2015), "El matemático afirma un gran avance en la teoría de la complejidad", Science , doi : 10.1126 / science.aad7416
- ^ a b Klarreich, Erica. "Algoritmo de referencia rompe el callejón sin salida de 30 años" . quantamagazine.org . Revista Quanta .
- ↑ Theory of Computing editors , consultado el 30 de julio de 2010.
- ^ Un gran resultado en isomorfismo gráfico // 4 de noviembre de 2015, un algoritmo de isomorfismo gráfico rápido // 11 de noviembre de 2015
- ^ El avance reclamado mata el problema de la informática clásica // Revisión de la tecnología del MIT, por Tom Simonite el 13 de noviembre de 2015
- ^ Babai, László (2016), "Graph Isomorphism in Quasipolynomial Time [Extended Abstract]", Actas del cuadragésimo octavo Simposio Anual de ACM sobre Teoría de la Computación (STOC '16) , Nueva York, NY, EE. UU.: ACM, págs. 684 –697, arXiv : 1512.03547 , doi : 10.1145 / 2897518.2897542 , ISBN 978-1-4503-4132-5
- ^ László Babai: Arreglando el caso UPCC de Split-or-Johnson , publicado el 14 de enero de 2017
- ^ Definición 2.3. El isomorfismo cadena , en: Las transacciones en Ciencias de la Computación V . Número especial sobre representación del conocimiento cognitivo. Editores en Jefe: Marina L. Gavrilova, CJ Kenneth Tan. Editores: Yingxu Wang, Keith Chan / Lecture Notes in Computer Science / Volumen 5540, Springer Verlag , 2009
- ^ Problema de intersección de Coset // Wiki de propiedades del grupo (beta)
- ^ Complejidad del problema de intersección de clases laterales // Intercambio teórico de la pila de informática, preguntado el 25 de septiembre de 2014 a las 9:43
- ^ 1993 Premio Gödel Archivado el 8 de diciembre de 2015 en la Wayback Machine , ACM SIGACT , consultado el14 de agosto de 2010.
- ^ Academia Estadounidense de Artes y Ciencias . Becarios 2015 y sus afiliaciones
enlaces externos
- Medios relacionados con László Babai en Wikimedia Commons
- Sitio web personal .
- MathSciNet: "Elementos creados por Babai, László". [ enlace muerto permanente ]
- DBLP: László Babai .