Бабаи, Ласло

Ласло Бабаи
венг. Babai László

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

Биография

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

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

Graph Isomorphism in Quasipolynomial Time

С 10 ноября по 1 декабря 2015 года на семинаре «Combinatorics and Theoretical Computer Science» в Чикагском университете сделал три доклада «Graph Isomorphism in Quasipolynomial Time», в которых изложил алгоритм, который решает проблему изоморфизма графов за квазиполиномиальный $\exp \left(P(\log (n))\right)$ период времени, где $n-$ количество вершин, $P(\log (n))-$ многочлен от $\log (n)$.

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

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

abstract

We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (under action group) (SI) and Coset Intersection (CI) can be solved in quasipolynomial

$\exp \left({(\log n)}^{O\left(1\right)}\right)$

time. The best previous bound for GI was

$\exp \left(O\left(\sqrt{n\log n}\right)\right)$

where

$n$

is the number of vertices (Luks, 1983); for the other two problems, the bound was similar,

$\exp \left(\tilde{O}\left(\sqrt{n}\right)\right)$

where

$n$

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.

См. также

• List of unsolved problems in computer science

Ссылки

• 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