Бабаи, Ласло

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Ласло Бабаи
венг. Babai László
Laszlo Babai.jpg
Дата рождения 20 июля 1950(1950-07-20) (72 года)
Место рождения
Страна
Научная сфера комбинаторика
Место работы
Альма-матер
Научный руководитель Туран, Пал и Шош, Вера[2]
Награды и премии
Сайт people.cs.uchicago.edu/~…
Логотип Викисклада Медиафайлы на Викискладе

Ласло Бабаи (венг. Babai László; род. 20 июля 1950, Будапешт)[3] — венгерский и американский учёный, профессор математики и информатики (computer science) в Чикагском университете. Его исследования сосредоточены в следующих отраслях: теория сложности вычислений, теория алгоритмов, комбинаторика, и конечные группы с акцентом на взаимодействие между этими отраслями. Автор более 180 научных трудов.[3]

Биография[править | править код]

Бабаи изучал математику в Будапештском университете имени Лоранда Этвёша с 1968 по 1973, получил Ph.D. в Венгерской академии наук в 1975, и получил D.Sc. в Венгерской академии наук в 1984.[3][4] В США работает с 1987 года.

Автор алгоритма Лас-Вегас (1979), версии метода Монте-Карло.[5]

Graph Isomorphism in Quasipolynomial Time[править | править код]

С 10 ноября по 1 декабря 2015 года на семинаре «Combinatorics and Theoretical Computer Science» в Чикагском университете сделал три доклада «Graph Isomorphism in Quasipolynomial Time», в которых изложил алгоритм, который решает проблему[en] изоморфизма графов за квазиполиномиальный период времени, где количество вершин, многочлен от .[6][7][8][9]

10 декабря 2015 опубликовано видео первого доклада[10].

11 декабря 2015 в arXiv.org опубликовал одноимённую статью «Graph Isomorphism in Quasipolynomial Time»[11].

См. также[править | править код]

Примечания[править | править код]

  1. http://news.uchicago.edu/profile/laszlo-babai
  2. 1 2 Математическая генеалогия (англ.) — 1997.
  3. 1 2 3 Curriculum vitae Архивировано 11 февраля 2014 года. // Babai’s web site Архивная копия от 7 ноября 2017 на Wayback Machine
  4. Бабаи, Ласло (англ.) в проекте «Математическая генеалогия»
  5. «'Ласло Бабаи»', Monte-Carlo algorithms in graph isomorphism testing Архивная копия от 8 декабря 2017 на Wayback Machine, Université de Montréal, D. M. S. № 79-10.
  6. Laszlo Babai (University of Chicago): Graph Isomorphism in Quasipolynomial Time I: The «Local Certificates Algorithm» // Combinatorics and Theoretical Computer Science seminar, 10 ноября 2015, 15:00 — 16:00
  7. A Big Result On Graph Isomorphism Архивная копия от 10 июля 2017 на Wayback Machine // November 4, 2015, A Fast Graph Isomorphism Algorithm Архивная копия от 29 июля 2017 на Wayback Machine // November 11, 2015
  8. Combinatorics and Theoretical Computer Science Архивировано 22 декабря 2015 года. calendar // Theoretical Computer Science at the University of Chicago Архивная копия от 22 октября 2017 на Wayback Machine. November 24, 2015, Laszlo Babai (University of Chicago): Graph Isomorphism in Quasipolynomial Time II: The Split-or-Johnson routine" (Combinatorics and TCS seminar)
  9. Claimed Breakthrough Slays Classic Computing Problem Архивная копия от 22 января 2016 на Wayback Machine // MIT Technology Review, by Tom Simonite on November 13, 2015
  10. Graph Isomorphism in Quasipolynomial Time I Архивная копия от 12 сентября 2018 на Wayback Machine, lecture seminar by László Babai on November 10, 2015. The University of Chicago // youtube, 1 час. 40 мин. Опубликовано 10 декабря 2015
  11. László Babai. Graph Isomorphism in Quasipolynomial Time, 84 pages / abstract Архивная копия от 22 ноября 2017 на Wayback Machine // arXiv.org > cs > arXiv:1512.03547 / version 1 [v1] Fri, 11 Dec 2015 08:04:26 GMT
  12. "'Definition 2.3."' String Isomorphism Архивная копия от 28 марта 2018 на Wayback Machine // Google Books, in: Transactions on Computational Science V Архивная копия от 29 марта 2018 на Wayback Machine. Special Issue on Cognitive Knowledge Representation. Editors-in-Chief: Marina L. Гаврилова, C. J. Kenneth Tan. Editors: Yingxu Wang, Keith Chan Архивная копия от 28 марта 2018 на Wayback Machine / Lecture Notes in Computer Science[en] / Volume 5540, Springer Verlag, 2009
  13. Coset intersection problem Архивная копия от 29 марта 2018 на Wayback Machine // The Group Properties Wiki Архивная копия от 22 октября 2017 на Wayback Machine (beta)
  14. Complexity of the coset intersection problem Архивная копия от 24 декабря 2015 на Wayback Machine // Theoretical Computer Science Stack Exchange
    Graph Isomorphism Problem Архивная копия от 29 марта 2018 на Wayback Machine // ibid.
    Complexity of simple undirected graph isomorphism problem Архивная копия от 29 марта 2018 на Wayback Machine // ibid.

Ссылки[править | править код]

copy Архивная копия от 4 марта 2016 на Wayback Machine from Lenta.ru // texnomaniya.ru, 20 ноября 2015
Опубликован быстрый алгоритм для задачи изоморфизма графов Архивная копия от 3 июля 2017 на Wayback Machine // Источник: Хабрахабр, переведено 16 декабря 2015, 06:30