Бабаи, Ласло
Шаблон:Учёный Ласло Бабаи (Шаблон:Lang-hu; род. Шаблон:ДР, Будапешт)[1] — венгерский и американский учёный, профессор математики и информатики (computer science) в Чикагском университете. Его исследования сосредоточены в следующих отраслях: теория сложности вычислений, теория алгоритмов, комбинаторика, и конечные группы с акцентом на взаимодействие между этими отраслями. Автор более 180 научных трудов.[1]
Биография
Бабаи изучал математику в Будапештском университете имени Лоранда Этвёша с 1968 по 1973 год, получил Ph.D. в Венгерской академии наук в 1975 году, и получил D.Sc. в Венгерской академии наук в 1984 году.[1][2] В США работает с 1987 года.
Автор алгоритма Лас-Вегас (1979), версии метода Монте-Карло.[3]
Graph Isomorphism in Quasipolynomial Time
С 10 ноября по 1 декабря 2015 года на семинаре «Combinatorics and Theoretical Computer Science» в Чикагском университете сделал три доклада «Graph Isomorphism in Quasipolynomial Time», в которых изложил алгоритм, который решает Шаблон:Iw изоморфизма графов за квазиполиномиальный период времени, где количество вершин, многочлен от .[4][5][6][7]
10 декабря 2015 года опубликовано видео первого доклада[8].
11 декабря 2015 года в arXiv.org опубликовал одноимённую статью «Graph Isomorphism in Quasipolynomial Time»[9]. Шаблон:Hider
См. также
Примечания
Ссылки
- 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 Шаблон:Wayback, by Adrian Cho 10 November 2015 17:45 // Posted in Math Шаблон:Wayback, Science AAAS News
- A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details Шаблон:Wayback + Background on Graph Isomorphism + The Main Result // Math ∩ Programming. Posted on November 12, 2015 by j2kun
- Landmark Algorithm Breaks 30-Year Impasse Шаблон:Wayback, Algorithm Solves Graph Isomorphism in Record Time // Quanta Magazine. By: Erica Klarreich, December 14, 2015
- A Little More on the Graph Isomorphism Algorithm Шаблон:Wayback // November 21, 2015, by RJLipton+KWRegan (Ken Regan and Dick Lipton)
- [Ласло] Бабай приблизился к решению «проблемы тысячелетия» Шаблон:Wayback // Наука Lenta.ru, 14:48, 20 ноября 2015
- copy Шаблон:Wayback from Lenta.ru // texnomaniya.ru, 20 ноября 2015
- Опубликован быстрый алгоритм для задачи изоморфизма графов Шаблон:Wayback // Анатолий Ализар, Хабрахабр, 16 декабря в 02:12
- Опубликован быстрый алгоритм для задачи изоморфизма графов Шаблон:Wayback // Источник: Хабрахабр, переведено 16 декабря 2015, 06:30
Шаблон:Вс Шаблон:Лауреаты премии Кнута Шаблон:Лауреаты премии Гёделя
- ↑ 1,0 1,1 1,2 Curriculum vitae Шаблон:Webarchive // Babai’s web site Шаблон:Wayback
- ↑ Шаблон:MathGenealogy
- ↑ «'Ласло Бабаи»', Monte-Carlo algorithms in graph isomorphism testing Шаблон:Wayback, 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 Шаблон:Wayback // November 4, 2015, A Fast Graph Isomorphism Algorithm Шаблон:Wayback // November 11, 2015
- ↑ Combinatorics and Theoretical Computer Science Шаблон:Webarchive calendar // Theoretical Computer Science at the University of Chicago Шаблон:Wayback. 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 Шаблон:Wayback // MIT Technology Review, by Tom Simonite on November 13, 2015
- ↑ Graph Isomorphism in Quasipolynomial Time I Шаблон:Wayback, 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 Шаблон:Wayback // arXiv.org > cs > arXiv:1512.03547 / version 1 [v1] Fri, 11 Dec 2015 08:04:26 GMT