PROFILPELAJAR.COM

Ласло Бабаи
Ласло Бабаи
	венг. Babai László
Дата рождения	20 июля 1950 (74 года)
Место рождения	Будапешт, Венгрия;
Страна	Венгрия;
Род деятельности	математик, специалист в области информатики, преподаватель университета
Научная сфера	комбинаторика, теория сложности вычислений, конечная группа и interactive proof system[вд]
Место работы	Чикагский университет;
Альма-матер	Будапештский университет (1973); Венгерская академия наук (1975); Fazekas Mihály Gimnázium[вд] (1968);
Научный руководитель	Пал Туран и Вера Шош
Награды и премии	Премия Гёделя (1993) премия Кнута (2015) премия Дейкстры (2016) премия Пала Эрдёша[вд]
Сайт	people.cs.uchicago.edu/~…
	Медиафайлы на Викискладе

Ласло Бабаи (венг. Babai László; род. 20 июля 1950 (1950-07-20), Будапешт)^[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», в которых изложил алгоритм, который решает проблему^[англ.] изоморфизма графов за квазиполиномиальный $\exp \left(P\left(\log(n)\right)\right)$ период времени, где $\displaystyle n\ -$ количество вершин, $P\left(\log(n)\right)\ -$ многочлен от $\log(n)$ .^[6]^[7]^[8]^[9]

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

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

abstract

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
$\exp \left(\left(\log n\right)^{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,
$\quad \qquad \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.