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