Бабаи, Ласло

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

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

Биография

Бабаи изучал математику в Будапештском университете имени Лоранда Этвёша с 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», в которых изложил алгоритм, который решает проблему изоморфизма графов за квазиполиномиальный период времени, где количество вершин, многочлен от .[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. Математическая генеалогия (англ.) — 1997.
  3. Curriculum vitae Архивировано 11 февраля 2014 года. // Babai’s web site
  4. Бабаи, Ласло (англ.) в проекте «Математическая генеалогия»
  5. «'Ласло Бабаи»', Monte-Carlo algorithms in graph isomorphism testing, 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 // November 4, 2015, A Fast Graph Isomorphism Algorithm // November 11, 2015
  8. Combinatorics and Theoretical Computer Science Архивировано 22 декабря 2015 года. calendar // Theoretical Computer Science at the University of Chicago. 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 // MIT Technology Review, by Tom Simonite on November 13, 2015
  10. Graph Isomorphism in Quasipolynomial Time I, 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 // arXiv.org > cs > arXiv:1512.03547 / version 1 [v1] Fri, 11 Dec 2015 08:04:26 GMT
  12. "'Definition 2.3."' String Isomorphism // Google Books, in: Transactions on Computational Science V. Special Issue on Cognitive Knowledge Representation. Editors-in-Chief: Marina L. Гаврилова, C. J. Kenneth Tan. Editors: Yingxu Wang, Keith Chan / Lecture Notes in Computer Science / Volume 5540, Springer Verlag, 2009
  13. Coset intersection problem // The Group Properties Wiki (beta)
  14. Complexity of the coset intersection problem // Theoretical Computer Science Stack Exchange
    Graph Isomorphism Problem // ibid.
    Complexity of simple undirected graph isomorphism problem // ibid.

Ссылки

copy from Lenta.ru // texnomaniya.ru, 20 ноября 2015
Опубликован быстрый алгоритм для задачи изоморфизма графов // Источник: Хабрахабр, переведено 16 декабря 2015, 06:30
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.