Бабаи, Ласло

Ласло Бабаи
венг. Babai László
Дата рождения	20 июля 1950(1950-07-20) (73 года)
Место рождения	Будапешт, Венгрия[1]
Страна	Венгрия
Род деятельности	математик, специалист в области информатики, преподаватель университета
Научная сфера	комбинаторика, теория сложности вычислений, конечная группа и interactive proof system[вд]
Место работы	Чикагский университет
Альма-матер	Будапештский университет (1973) Венгерская академия наук (1975)[2] Fazekas Mihály Gimnázium[вд] (1968)
Научный руководитель	Пал Туран и Вера Шош[2]
Награды и премии	Премия Гёделя (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», в которых изложил алгоритм, который решает проблему^[англ.] изоморфизма графов за квазиполиномиальный ${\displaystyle \exp \left(P\left(\log(n)\right)\right)}$ период времени, где ${\displaystyle \displaystyle n\ -}$ количество вершин, ${\displaystyle P\left(\log(n)\right)\ -}$ многочлен от ${\displaystyle \log(n)}$.^[6][7][8][9]

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

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

См. также

• 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

Эта страница в последний раз была отредактирована 19 марта 2022 в 20:02.