Interested Article - Бабаи, Ласло

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

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

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

abstract

We show that the Graph Isomorphism and the related problems of String Isomorphism (under action group) (SI) and Coset Intersection (CI) 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 ( , 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, are the only obstructions to effective canonical partitioning.

См. также

Примечания

↑ (англ.) — 1997.
↑ 11 февраля 2014 года. // от 7 ноября 2017 на Wayback Machine
(англ.) в проекте « Математическая генеалогия »
«'Ласло Бабаи»', от 8 декабря 2017 на Wayback Machine , Université de Montréal, D. M. S. № 79-10.
Laszlo Babai (University of Chicago): : The «Local Certificates Algorithm» // Combinatorics and Theoretical Computer Science seminar, 10 ноября 2015, 15:00 — 16:00
от 10 июля 2017 на Wayback Machine // November 4, 2015, от 29 июля 2017 на Wayback Machine // November 11, 2015
22 декабря 2015 года. calendar // от 22 октября 2017 на Wayback Machine . November 24, 2015, Laszlo Babai (University of Chicago): Graph Isomorphism in Quasipolynomial Time II: The Split-or-Johnson routine" (Combinatorics and TCS seminar)
от 22 января 2016 на Wayback Machine // MIT Technology Review, by Tom Simonite on November 13, 2015
от 12 сентября 2018 на Wayback Machine , lecture seminar by László Babai on November 10, 2015. The University of Chicago // youtube, 1 час. 40 мин. Опубликовано 10 декабря 2015
László Babai. , 84 pages / от 22 ноября 2017 на Wayback Machine // arXiv.org > cs > arXiv:1512.03547 / version 1 [v1] Fri, 11 Dec 2015 08:04:26 GMT
от 28 марта 2018 на Wayback Machine // Google Books, in: от 29 марта 2018 на Wayback Machine . Special Issue on Cognitive Knowledge Representation. от 28 марта 2018 на Wayback Machine / / Volume 5540, Springer Verlag , 2009
от 29 марта 2018 на Wayback Machine // от 22 октября 2017 на Wayback Machine (beta)
от 24 декабря 2015 на Wayback Machine // Theoretical Computer Science Stack Exchange
от 29 марта 2018 на Wayback Machine // ibid.
от 29 марта 2018 на Wayback Machine // ibid.

Ссылки

// Published on Nov 20, 2015 Division of the Physical Sciences / The University of Chicago
от 12 января 2016 на Wayback Machine , by Adrian Cho 10 November 2015 17:45 // Posted in от 16 октября 2015 на Wayback Machine , Science News
от 17 сентября 2017 на Wayback Machine + Background on Graph Isomorphism + The Main Result // Math ∩ Programming. Posted on November 12, 2015 by j2kun
от 25 апреля 2017 на Wayback Machine , Algorithm Solves Graph Isomorphism in Record Time // Quanta Magazine. By: Erica Klarreich, December 14, 2015
от 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

от 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

[_2c595974451d1316-2] (англ.) — 1997.

[cv-3] 11 февраля 2014 года. // от 7 ноября 2017 на Wayback Machine

[4] (англ.) в проекте « Математическая генеалогия »

[5] «'Ласло Бабаи»', от 8 декабря 2017 на Wayback Machine , Université de Montréal, D. M. S. № 79-10.

[6] Laszlo Babai (University of Chicago): : The «Local Certificates Algorithm» // Combinatorics and Theoretical Computer Science seminar, 10 ноября 2015, 15:00 — 16:00

[7] от 10 июля 2017 на Wayback Machine // November 4, 2015, от 29 июля 2017 на Wayback Machine // November 11, 2015

[8] 22 декабря 2015 года. calendar // от 22 октября 2017 на Wayback Machine . November 24, 2015, Laszlo Babai (University of Chicago): Graph Isomorphism in Quasipolynomial Time II: The Split-or-Johnson routine" (Combinatorics and TCS seminar)

[9] от 22 января 2016 на Wayback Machine // MIT Technology Review, by Tom Simonite on November 13, 2015

[10] от 12 сентября 2018 на Wayback Machine , lecture seminar by László Babai on November 10, 2015. The University of Chicago // youtube, 1 час. 40 мин. Опубликовано 10 декабря 2015

[11] László Babai. , 84 pages / от 22 ноября 2017 на Wayback Machine // arXiv.org > cs > arXiv:1512.03547 / version 1 [v1] Fri, 11 Dec 2015 08:04:26 GMT

[12] от 28 марта 2018 на Wayback Machine // Google Books, in: от 29 марта 2018 на Wayback Machine . Special Issue on Cognitive Knowledge Representation. от 28 марта 2018 на Wayback Machine / / Volume 5540, Springer Verlag , 2009

[13] от 29 марта 2018 на Wayback Machine // от 22 октября 2017 на Wayback Machine (beta)

[14] от 24 декабря 2015 на Wayback Machine // Theoretical Computer Science Stack Exchange
от 29 марта 2018 на Wayback Machine // ibid.
от 29 марта 2018 на Wayback Machine // ibid.

Лауреаты премии Гёделя
1990-е	1993 Гольдвассер Микали Моран 1994 1995 1996 1997 Мозес 1998 1999 Шор
2000-е	2000 Варди 2001 Арора Фейге Гольдвассер Ловас Мотвани Судан 2002 2003 2004 Херлихи Шавит Захароглу 2005 Алон 2006 2007 Разборов 2008 Тэн Шанхуа Спилмен 2009 Вигдерзон
2010-е	2010 Арора Митчелл 2011 2012 Пападимитриу Тардош 2013 Боне 2014 2015 Спилмен Тэн Шанхуа 2016 2017 Дворк 2018 Регев 2019
2020-е	2020 2021 Булатов 2022

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

Дата рождения	20 июля 1950 ( 1950-07-20 ) (73 года)
Место рождения	Будапешт , Венгрия
Страна	Венгрия
Научная сфера	комбинаторика , теория сложности вычислений , конечная группа и
Место работы	Чикагский университет
Альма-матер	Будапештский университет ( 1973 ) Венгерская академия наук ( 1975 ) ( 1968 )
Научный руководитель	Пал Туран и Вера Шош
Награды и премии	Премия Гёделя ( 1993 ) премия Кнута ( 2015 ) премия Дейкстры ( 2016 )
Сайт

Биография

Graph Isomorphism in Quasipolynomial Time

См. также

Примечания

Ссылки

Дивизия «Святой Ласло»

Чех, Ласло

Ласло IV Кун

Same as Бабаи, Ласло

Бабаи (Харьковская область)

Восстание бабаи

Дивизия «Святой Ласло»

Чех, Ласло

Ласло IV Кун

Немет, Ласло

Берти, Ласло

Райчаньи, Ласло

Бенедек, Ласло

Ласло, Хана

Ласло IV Кун

Соллаш, Ласло

Бёлёни, Ласло

Бёлёни, Ласло

Балинт, Ласло

Биро, Ласло

Тот, Ласло (вандал)

Русняк, Ласло

Пирош, Ласло

Мохой-Надь, Ласло

Лукач, Ласло

Бардоши, Ласло

Папп, Ласло

Алмаши, Ласло

Будаи, Ласло

Фазекаш, Ласло

Чех, Ласло (футболист)

Беллак, Ласло

Бито, Ласло

Бодроги, Ласло

Мохой-Надь, Ласло

Дьёре, Ласло

Дьёре, Ласло

Ласло, Дьюла

Ласло III

Немеш, Ласло

Райк, Ласло

Фидель, Ласло

Меднянский, Ласло

Халас, Ласло

Бенеш, Ласло

Секей, Ласло

Хаммерль, Ласло

Тёкеш, Ласло