Babai, Laszló

Laszlo Babai
colgado. Babai Laszló
Fecha de nacimiento 20 de julio de 1950( 20 de julio de 1950 ) (72 años)
Lugar de nacimiento
País
Esfera científica combinatoria
Lugar de trabajo
alma mater
consejero científico Turan, Pal y Shosh, Vera [2]
Premios y premios Premio Gödel ( 1993 ) Premio Knuth ( 2015 )
Sitio web people.cs.uchicago.edu/~…
 Archivos multimedia en Wikimedia Commons

Laszlo Babai ( húngaro Babai László ; nacido el 20 de julio de 1950 en Budapest ) [3]  es un científico húngaro y estadounidense, profesor de matemáticas e informática en la Universidad de Chicago . Su investigación se centra en las siguientes ramas: teoría de la complejidad computacional , teoría de algoritmos , combinatoria y grupos finitos con énfasis en las interacciones entre estas ramas. Autor de más de 180 artículos científicos. [3]

Biografía

Babai estudió matemáticas en la Universidad Eötvös Loránd de Budapest de 1968 a 1973 y recibió un doctorado. en la Academia Húngara de Ciencias en 1975 y recibió un D.Sc. en la Academia Húngara de Ciencias en 1984. [3] [4] Trabaja en los Estados Unidos desde 1987.

Autor del algoritmo de Las Vegas (1979), una versión del método Monte Carlo . [5]

Isomorfismo de grafos en tiempo cuasipolinomial

Del 10 de noviembre al 1 de diciembre de 2015, en el seminario "Combinatorics and Theoretical Computer Science" de la Universidad de Chicago, realizó tres ponencias "Graph Isomorphism in Quasipolynomial Time ", en las que delineó un algoritmo que resuelve el problema de isomorfismo gráfico en un período de tiempo cuasi -polinomio, donde número de vértices, polinomio en . [6] [7] [8] [9]

El 10 de diciembre de 2015 se publicó un video del primer reportaje [10] .

El 11 de diciembre de 2015 se publicó en arXiv.org un artículo del mismo nombre "Graph Isomorphism in Quasipolynomial Time" [11] .

resumen

Mostramos que el problema de isomorfismo de grafos (GI) y los problemas relacionados de isomorfismo de cuerdas [12] (bajo el grupo de acción) (SI) y la intersección de clases laterales (CI) [13] [14] pueden resolverse en cuasipolinomios.

tiempo. El mejor límite anterior para GI fue

donde es 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 para el grupo de algoritmos de Luks mediante "certificados locales teóricos y técnicas de partición canónica combinatoria". Mostramos que, en un sentido bien definido, los gráficos de Johnson son ​​los únicos obstáculos para una partición canónica efectiva.

Véase también

  • Lista de problemas no resueltos en informática

Notas

  1. ↑ http://news.uchicago.edu/profile/laszlo-babai
  2. ↑ 1 2 Genealogía matemática  (inglés) - 1997.
  3. ↑ 1 2 3 Curriculum vitae Archivado el 11 de febrero de 2014. // Sitio web de Babai Archivado el 7 de noviembre de 2017 en Wayback Machine .
  4. ↑ Babai, Laszlo  (ing.) en el Proyecto de genealogía matemática
  5. ↑ "'Laszlo Babai'", Algoritmos de Montecarlo en pruebas de isomorfismo de grafos Archivado el 8 de diciembre de 2017 en Wayback Machine , Université de Montréal, DMS n.º 79-10 .
  6. ↑ Laszlo Babai (Universidad de Chicago): Isomorfismo de gráficos en tiempo cuasipolinomial I : el "algoritmo de certificados locales" // Seminario de combinatoria e informática teórica, 10 de noviembre de 2015, 15:00 - 16:00
  7. ↑ A Big Result On Graph Isomorphism Archivado el 10 de julio de 2017 en Wayback Machine // 4 de noviembre de 2015, A Fast Graph Isomorphism Algorithm Archivado el 29 de julio de 2017 en Wayback Machine // 11 de noviembre de 2015
  8. ↑ Combinatorics and Theoretical Computer Science Archivado el 22 de diciembre de 2015. calendario // Ciencias de la computación teórica en la Universidad de Chicago Archivado el 22 de octubre de 2017 en Wayback Machine . 24 de noviembre de 2015, Laszlo Babai (Universidad de Chicago): Isomorfismo gráfico en tiempo cuasipolinomial II: La rutina Split-or-Johnson" (seminario Combinatorics y TCS)
  9. ↑ Claimed Breakthrough Slays Classic Computing Problem Archivado el 22 de enero de 2016 en Wayback Machine // MIT Technology Review, por Tom Simonite el 13 de noviembre de 2015
  10. ↑ Graph Isomorphism in Quasipolynomial Time I Archivado el 12 de septiembre de 2018 en Wayback Machine , seminario de conferencias de László Babai el 10 de noviembre de 2015. The University of Chicago // youtube, 1 hora. 40 minutos Publicado el 10 de diciembre de 2015
  11. ↑ Laszlo Babai. Isomorfismo de grafos en tiempo cuasipolinomial , 84 páginas/ resumen Archivado el 22 de noviembre de 2017 en Wayback Machine // arXiv.org > cs > arXiv:1512.03547 / versión 1 [v1] Vie, 11 de diciembre de 2015 08:04:26 GMT
  12. ↑ "'Definition 2.3."' String Isomorphism Archivado el 28 de marzo de 2018 en Wayback Machine // Google Books, en: Transactions on Computational Science V Archivado el 29 de marzo de 2018 en Wayback Machine . Edición especial sobre representación cognitiva del conocimiento. Editores en jefe: Marina L. Gavrilova, CJ Kenneth Tan. Editores: Yingxu Wang, Keith Chan Archivado el 28 de marzo de 2018 en Wayback Machine / Lecture Notes in Computer Science / Volume 5540, Springer Verlag , 2009
  13. ↑ Problema de intersección de clases laterales Archivado el 29 de marzo de 2018 en Wayback Machine // The Group Properties Wiki Archivado el 22 de octubre de 2017 en Wayback Machine (beta)
  14. ↑ Complejidad del problema de intersección de clases laterales Archivado el 24 de diciembre de 2015 en Wayback Machine // Theoretical Computer Science Stack Exchange
    Graph Isomorphism Problem Archivado el 29 de marzo de 2018 en Wayback Machine // ibíd.
    Complejidad del problema de isomorfismo de gráfico no dirigido simple Archivado el 29 de marzo de 2018 en Wayback Machine // ibíd.

Enlaces

copia Copia de archivo fechada el 4 de marzo de 2016 en Wayback Machine de Lenta.ru // texnomaniya.ru, 20 de noviembre de 2015 Se ha publicado un algoritmo rápido para el problema de isomorfismo de gráficos . Archivado el 3 de julio de 2017 en Wayback Machine .
  Ir al elemento de Wikidata  sitios temáticos
En catálogos bibliográficos
 Ganadores del premio Knuth