László Babai

Matemático e informático húngaro.

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 , algoritmos , combinatoria y grupos finitos , con énfasis en las interacciones entre estos campos.

Vida

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 de Ciencias de Hungría en 1975 y un doctorado en Ciencias de la Academia de Ciencias de Hungría en 1984. ^{[1] [2]} Ocupó puesto docente 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ó a trabajar conjuntamente en el departamento de matemáticas de Chicago y renunció a su puesto en Eötvös Loránd. ^[1]

Trabajar

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 grupos en las pruebas de isomorfismo de gráficos . ^[4] En noviembre de 2015, anunció un algoritmo de tiempo cuasipolinomial para el problema de isomorfismo gráfico . ^{[5] [6]}

Es editor en jefe de la revista arbitrada en línea 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.

Isomorfismo gráfico 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 cuasipolinomial 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]

abstracto

Mostramos que el problema de isomorfismo de grafos (GI) y los problemas relacionados de isomorfismo de cadenas ^[12] (bajo acción grupal) (SI) e intersección de Coset (CI) ^{[13] [14]} se pueden resolver en tiempo cuasipolinomial. El mejor límite anterior para GI era dónde está el número de vértices ( Luks , 1983); para los otros dos problemas, el límite fue 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 del algoritmo de Luks mediante «certificados locales» teóricos de grupo y técnicas combinatorias de partición canónica. Mostramos que, en un sentido bien definido, los gráficos de Johnson son los únicos obstáculos para una partición canónica efectiva. ${\displaystyle \exp \left(\left(\log n\right)^{O\left(1\right)}\right)}$ ${\displaystyle \exp \left(O\left({\sqrt {n\log n}}\right)\right),}$ ${\displaystyle n}$ ${\displaystyle \quad \qquad \exp \left({\tilde {O}}\left({\sqrt {n}}\right)\right),}$ ${\displaystyle n}$

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 artículos 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 de Kyoto (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 gráficos // Publicado el 20 de noviembre de 2015 División de Ciencias Físicas / Universidad de Chicago
• Un matemático afirma haber logrado un gran avance en la teoría de la complejidad, por Adrian Cho 10 de noviembre de 2015 17:45 // Publicado en Matemáticas, Ciencias AAAS News
• Un algoritmo de tiempo cuasipolinomial para el isomorfismo de gráficos: los detalles + antecedentes sobre el isomorfismo de gráficos + el resultado principal // Programación matemática ∩. Publicado el 12 de noviembre de 2015 por j2kun
• Un poco más sobre el algoritmo de isomorfismo gráfico // 21 de noviembre de 2015, por RJLipton+KWRegan (Ken Regan y Dick Lipton)

copia de Lenta.ru // texnomaniya.ru, 20 de noviembre de 2015

• Опубликован быстрый алгоритм для задачи изоморфизма графов // Анатолий Ализар, Хабрахабр, 16 de diciembre a las 02:12

Опубліковано швидкий алгоритм для задачі ізоморфізму графів Archivado el 3 de julio de 2017 en Wayback Machine // Джерело: Хабрахабр, перекладено 16 грудня 2015, 06:30

Referencias

1. Curriculum vitae del sitio web de Babai, consultado el 28 de enero de 2016.
2. László Babai en el Proyecto Genealogía de Matemáticas
3. 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. Sistema. Ciencia. , 36 (2): 254–276, doi : 10.1016/0022-0000(88)90028-1.
4. Babai, László (1979), Algoritmos de Monte-Carlo en pruebas de isomorfismo de gráficos (PDF) , Tech. Informe, Universidad de Montreal.
5. Cho, Adrian (10 de noviembre de 2015), "Matemático afirma un gran avance en la teoría de la complejidad", Ciencia , doi :10.1126/science.aad7416
6. Klarreich, Erica (14 de diciembre de 2015). "Un algoritmo histórico rompe un estancamiento de 30 años". Revista Quanta . Archivado desde el original el 21 de enero de 2016.
7. Editores de Teoría de la Computación, consultado el 30 de julio de 2010.
8. Un gran resultado sobre isomorfismo de gráficos // 4 de noviembre de 2015, Un algoritmo de isomorfismo de gráficos rápido // 11 de noviembre de 2015
9. Un avance afirmado elimina el problema de la informática clásica Archivado el 22 de enero de 2016 en Wayback Machine // MIT Technology Review, por Tom Simonite el 13 de noviembre de 2015
10. Babai, László (2016), "Isomorfismo gráfico en tiempo cuasipolinomial [resumen extendido]", Actas del cuadragésimo octavo simposio anual 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, S2CID  17118954
11. László Babai: Arreglando el caso UPCC de Split-or-Johnson, publicado el 14 de enero de 2017
12. Definición 2.3. Isomorfismo de cuerdas, en: Transactions on Computational Science V. Número especial sobre representación del conocimiento cognitivo. Editores en jefe: Marina L. Gavrilova , CJ Kenneth Tan. Editores: Yingxu Wang, Keith Chan] / Apuntes de conferencias sobre informática / Volumen 5540, Springer Verlag , 2009
13. Problema de intersección de Coset // The Group Properties Wiki (beta)
14. Complejidad del problema de la intersección de coset // Intercambio de pilas de informática teórica, consultado el 25 de septiembre de 2014 a las 9:43
15. Premio Gödel 1993 Archivado el 8 de diciembre de 2015 en Wayback Machine , ACM SIGACT , consultado el 14 de agosto de 2010.
16. Academia Estadounidense de Artes y Ciencias . Becarios de 2015 y sus afiliaciones

enlaces externos

• Sitio web personal.
• DBLP: László Babai.