Бабаи, Ласло
Ласло Бабаи (венг. Babai László; род. 20 июля 1950, Будапешт)[3] — венгерский и американский учёный, профессор математики и информатики (computer science) в Чикагском университете. Его исследования сосредоточены в следующих отраслях: теория сложности вычислений, теория алгоритмов, комбинаторика, и конечные группы с акцентом на взаимодействие между этими отраслями. Автор более 180 научных трудов.[3]
Ласло Бабаи | |
---|---|
венг. Babai László | |
Дата рождения | 20 июля 1950 (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].
We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism[12] (under action group) (SI) and Coset Intersection (CI)[13][14] can be solved in quasipolynomial
time. The best previous bound for GI was
where is the number of vertices (Luks, 1983); for the other two problems, the bound was similar,
where is the size of the permutation domain (Babai, 1983).
The algorithm builds on Luks's SI framework and attacks the barrier configurations for Luks's algorithm group by theoretic «local certificates and combinatorial canonical partitioning techniques. We show that in a well-defined sense, Johnson graphs are the only obstructions to effective canonical partitioning.
Примечания
- http://news.uchicago.edu/profile/laszlo-babai
- Математическая генеалогия (англ.) — 1997.
- Curriculum vitae Архивировано 11 февраля 2014 года. // Babai’s web site
- Бабаи, Ласло (англ.) в проекте «Математическая генеалогия»
- «'Ласло Бабаи»', Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D. M. S. № 79-10.
- 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
- A Big Result On Graph Isomorphism // November 4, 2015, A Fast Graph Isomorphism Algorithm // November 11, 2015
- 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)
- Claimed Breakthrough Slays Classic Computing Problem // MIT Technology Review, by Tom Simonite on November 13, 2015
- 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
- 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
- "'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
- Coset intersection problem // The Group Properties Wiki (beta)
- Complexity of the coset intersection problem // Theoretical Computer Science Stack Exchange
Graph Isomorphism Problem // ibid.
Complexity of simple undirected graph isomorphism problem // ibid.
Ссылки
- Professor László Babai’s algorithm is next big step in conquering isomorphism in graphs // Published on Nov 20, 2015 Division of the Physical Sciences / The University of Chicago
- Mathematician claims breakthrough in complexity theory, by Adrian Cho 10 November 2015 17:45 // Posted in Math, Science AAAS News
- A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details + Background on Graph Isomorphism + The Main Result // Math ∩ Programming. Posted on November 12, 2015 by j2kun
- Landmark Algorithm Breaks 30-Year Impasse, Algorithm Solves Graph Isomorphism in Record Time // Quanta Magazine. By: Erica Klarreich, December 14, 2015
- A Little More on the Graph Isomorphism Algorithm // November 21, 2015, by RJLipton+KWRegan (Ken Regan and Dick Lipton)
- [Ласло] Бабай приблизился к решению «проблемы тысячелетия» // Наука Lenta.ru, 14:48, 20 ноября 2015
- copy from Lenta.ru // texnomaniya.ru, 20 ноября 2015
- Опубликован быстрый алгоритм для задачи изоморфизма графов // Анатолий Ализар, Хабрахабр, 16 декабря в 02:12
- Опубликован быстрый алгоритм для задачи изоморфизма графов // Источник: Хабрахабр, переведено 16 декабря 2015, 06:30