Бабаи, Ласло
Ласло Бабаи | |
---|---|
венг. Babai László | |
![]() | |
Дата рождения | 20 июля 1950 (74 года) |
Место рождения | |
Страна | |
Род деятельности | математик, специалист в области информатики, преподаватель университета |
Научная сфера | комбинаторика, теория сложности вычислений, конечная группа и interactive proof system[вд] |
Место работы | |
Альма-матер |
|
Научный руководитель | Пал Туран и Вера Шош[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», в которых изложил алгоритм, который решает проблему[англ.] изоморфизма графов за квазиполиномиальный период времени, где количество вершин, многочлен от .[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
- ↑ 1 2 Mathematics Genealogy Project (англ.) — 1997.
- ↑ 1 2 3 Curriculum vitae Архивировано 11 февраля 2014 года. // Babai’s web site Архивная копия от 7 ноября 2017 на Wayback Machine
- ↑ Бабаи, Ласло (англ.) в проекте «Математическая генеалогия»
- ↑ «'Ласло Бабаи»', Monte-Carlo algorithms in graph isomorphism testing Архивная копия от 8 декабря 2017 на Wayback Machine, 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 Архивная копия от 10 июля 2017 на Wayback Machine // November 4, 2015, A Fast Graph Isomorphism Algorithm Архивная копия от 29 июля 2017 на Wayback Machine // November 11, 2015
- ↑ 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)
- ↑ Claimed Breakthrough Slays Classic Computing Problem Архивная копия от 22 января 2016 на Wayback Machine // MIT Technology Review, by Tom Simonite on November 13, 2015
- ↑ 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
- ↑ 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
- ↑ "'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[англ.] / Volume 5540, Springer Verlag, 2009
- ↑ Coset intersection problem Архивная копия от 29 марта 2018 на Wayback Machine // The Group Properties Wiki Архивная копия от 22 октября 2017 на Wayback Machine (beta)
- ↑ 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.
Ссылки
[править | править код]- 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 Архивная копия от 12 января 2016 на Wayback Machine, by Adrian Cho 10 November 2015 17:45 // Posted in Math Архивная копия от 16 октября 2015 на Wayback Machine, Science AAAS News
- A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details Архивная копия от 17 сентября 2017 на Wayback Machine + Background on Graph Isomorphism + The Main Result // Math ∩ Programming. Posted on November 12, 2015 by j2kun
- Landmark Algorithm Breaks 30-Year Impasse Архивная копия от 25 апреля 2017 на Wayback Machine, Algorithm Solves Graph Isomorphism in Record Time // Quanta Magazine. By: Erica Klarreich, December 14, 2015
- A Little More on the Graph Isomorphism Algorithm Архивная копия от 10 июля 2017 на Wayback Machine // November 21, 2015, by RJLipton+KWRegan (Ken Regan and Dick Lipton)
- [Ласло] Бабай приблизился к решению «проблемы тысячелетия» Архивная копия от 30 мая 2016 на Wayback Machine // Наука Lenta.ru, 14:48, 20 ноября 2015
- copy Архивная копия от 4 марта 2016 на Wayback Machine from Lenta.ru // texnomaniya.ru, 20 ноября 2015
- Опубликован быстрый алгоритм для задачи изоморфизма графов Архивная копия от 7 августа 2016 на Wayback Machine // Анатолий Ализар, Хабрахабр, 16 декабря в 02:12
- Опубликован быстрый алгоритм для задачи изоморфизма графов Архивная копия от 3 июля 2017 на Wayback Machine // Источник: Хабрахабр, переведено 16 декабря 2015, 06:30