Ласло Бабай

Ласло Бабай
Ласло Бабай
угор. Babai László
Народився	20 липня 1950 (74 роки); Будапешт, Угорська Народна Республіка
Країна	Угорщина
Національність	угорець
Діяльність	математик, інформатик, викладач університету
Alma mater	Університет Лоранда Етвеша , ; Угорська академія наук
Галузь	математика
Заклад	Чиказький університет
Науковий керівник	Пал Туран і Віра Шош
Аспіранти, докторанти	Маріо Жегедіd; Gábor Tardosd; Carsten Lundd; Péter Hajnald; Péter Pál Pálfyd; Barry Guidulid; José Augusto Ramos Soaresd; Tamás Lengyeld; Lajos Rónyaid; Albert J. Goodmand; Robert M. Bealsd; Satyanarayana V. Lokamd; Peter Kimmeld; Daniel Štefankovičd; Evelin Toumpakarid; Samuel Kutind; Thomas Hayesd; Katalin Friedld; Murali Krishnan Ganapathyd; Aytek Erdild; Sourav Chakrabortyd; Paolo Codenottid; Youming Qiaod; John Wilmesd
Членство	Угорська академія наук; Американська академія мистецтв і наук
Нагороди	Премія Геделя (1993) ; Премія Кнута (2015)
Особ. сторінка	László Babai
	Ласло Бабай у Вікісховищі

Ласло Бабай (угор. Babai László; 20 липня 1950(19500720), Будапешт)^[3] — угорський та американський математик, професор математики та інформатики (computer science) в Чиказькому університеті. Його дослідження зосереджені у галузях: теорія складності обчислень, теорія алгоритмів, комбінаторика, та скінченні групи, з наголосом на взаємодію між цими галузями. Автор понад 180 академічних праць.^[3]

Бабай вивчав математику в Будапештському університеті імені Лоранда Етвеша з 1968 по 1973, отримав Ph.D. в Угорській академії наук у 1975, і отримав D.Sc. в Угорській академії наук у 1984.^[3]^[4]

Автор алгоритму Лас-Вегас (1979), версії методу Монте-Карло.^[5]

Graph Isomorphism in Quasipolynomial Time

З 10 листопада по 1 грудня 2015 року на семінарі «Combinatorics and Theoretical Computer Science» в Чиказькому університеті зробив три доповіді «Graph Isomorphism in Quasipolynomial Time», у яких виклав алгоритм, який вирішує проблему^[en] ізоморфізму графів за квазіполіноміальний $e^{\log(n)^{O(1)}}$ час.^[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^[en] and the related problems of String Isomorphism^[12] (under group action) (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^[en], 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 by group 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.

Джерела

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

Див. також

Примітки

↑ http://news.uchicago.edu/profile/laszlo-babai
↑ ^а ^б ^в ^г ^д ^е ^ж ^и ^к ^л ^м ^н ^п ^р ^с ^т ^у ^ф ^х ^ц ^ш ^щ ^ю Математичний генеалогічний проєкт — 1997.
d:Track:Q829984
↑ ^а ^б ^в Curriculum vitae [Архівовано 11 лютого 2014 у Wayback Machine.] // Babai's web site [Архівовано 7 листопада 2017 у Wayback Machine.]
↑ Ласло Бабай(англ.) у проєкті «Математична генеалогія».
↑ Ласло Бабай, Monte-Carlo algorithms in graph isomorphism testing [Архівовано 8 грудня 2017 у Wayback Machine.], Université de Montréal, D.M.S. No. 79-10.
↑ 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:00
↑ A Big Result On Graph Isomorphism [Архівовано 10 липня 2017 у Wayback Machine.] // November 4, 2015, A Fast Graph Isomorphism Algorithm [Архівовано 29 липня 2017 у Wayback Machine.] // November 11, 2015
↑ Combinatorics and Theoretical Computer Science [Архівовано 22 грудня 2015 у Wayback Machine.] calendar // Theoretical Computer Science at the University of Chicago [Архівовано 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)
↑ Claimed Breakthrough Slays Classic Computing Problem [Архівовано 22 січня 2016 у Wayback Machine.] // MIT Technology Review, by Tom Simonite on November 13, 2015
↑ Graph Isomorphism in Quasipolynomial Time I [Архівовано 12 вересня 2018 у Wayback Machine.], seminar lecture by László Babai on November 10, 2015. The University of Chicago // youtube, 1 год. 40 хв. Опубліковано 10 грудня 2015
↑ László Babai. Graph Isomorphism in Quasipolynomial Time, 84 pages / abstract [Архівовано 22 листопада 2017 у Wayback Machine.] // arXiv.org > cs > arXiv:1512.03547 / version 1 [v1] Fri, 11 Dec 2015 08:04:26 GMT
↑ Definition 2.3. String Isomorphism [Архівовано 28 березня 2018 у Wayback Machine.] // Google Books, in: Transactions on Computational Science V [Архівовано 29 березня 2018 у Wayback Machine.]. Special Issue on Cognitive Knowledge Representation. Editors-in-Chief: Marina L. Gavrilova, C. J. Kenneth Tan. Editors: Yingxu Wang, Keith Chan [Архівовано 28 березня 2018 у Wayback Machine.] / Lecture Notes in Computer Science^[en] / Volume 5540, Springer Verlag, 2009
↑ Coset intersection problem [Архівовано 29 березня 2018 у Wayback Machine.] // The Group Properties Wiki [Архівовано 22 жовтня 2017 у Wayback Machine.] (beta)
↑ Complexity of the coset intersection problem [Архівовано 24 грудня 2015 у Wayback Machine.] // Theoretical Computer Science Stack Exchange
Graph Isomorphism Problem [Архівовано 29 березня 2018 у Wayback Machine.] // ibid.
Complexity of simple undirected graph isomorphism problem [Архівовано 29 березня 2018 у Wayback Machine.] // ibid.

[[http://news.uchicago.edu/profile/laszlo-babai_http://news.uchicago.edu/profile/laszlo-babai]<span_class="wef_low_priority_links"></span><div_style="display:none"></div>-1] ttp://news.uchicago.edu/profile/laszlo-babai

[<span_class="wikidata_cite_citetype_Q7094076_citetype_Q33002955_citetype_Q114955954"_data-entity-id="Q829984">Математичний_генеалогічний_проєкт<span_class="wef_low_priority_links">_—_1997.</span></span><div_style="display:none">[[d:Track:Q829984]]</div>-2] а ^б ^в ^г ^д ^е ^ж ^и ^к ^л ^м ^н ^п ^р ^с ^т ^у ^ф ^х ^ц ^ш ^щ ^ю Математичний генеалогічний проєкт — 1997.
d:Track:Q829984

[cv-3] а ^б ^в Curriculum vitae [Архівовано 11 лютого 2014 у Wayback Machine.] // Babai's web site [Архівовано 7 листопада 2017 у Wayback Machine.]

[4] Ласло Бабай(англ.) у проєкті «Математична генеалогія».

[5] Ласло Бабай, Monte-Carlo algorithms in graph isomorphism testing [Архівовано 8 грудня 2017 у Wayback Machine.], Université de Montréal, D.M.S. No. 79-10.

[6] 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:00

[7] A Big Result On Graph Isomorphism [Архівовано 10 липня 2017 у Wayback Machine.] // November 4, 2015, A Fast Graph Isomorphism Algorithm [Архівовано 29 липня 2017 у Wayback Machine.] // November 11, 2015

[8] Combinatorics and Theoretical Computer Science [Архівовано 22 грудня 2015 у Wayback Machine.] calendar // Theoretical Computer Science at the University of Chicago [Архівовано 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] Claimed Breakthrough Slays Classic Computing Problem [Архівовано 22 січня 2016 у Wayback Machine.] // MIT Technology Review, by Tom Simonite on November 13, 2015

[10] Graph Isomorphism in Quasipolynomial Time I [Архівовано 12 вересня 2018 у Wayback Machine.], seminar lecture by László Babai on November 10, 2015. The University of Chicago // youtube, 1 год. 40 хв. Опубліковано 10 грудня 2015

[11] László Babai. Graph Isomorphism in Quasipolynomial Time, 84 pages / abstract [Архівовано 22 листопада 2017 у Wayback Machine.] // arXiv.org > cs > arXiv:1512.03547 / version 1 [v1] Fri, 11 Dec 2015 08:04:26 GMT

[12] Definition 2.3. String Isomorphism [Архівовано 28 березня 2018 у Wayback Machine.] // Google Books, in: Transactions on Computational Science V [Архівовано 29 березня 2018 у Wayback Machine.]. Special Issue on Cognitive Knowledge Representation. Editors-in-Chief: Marina L. Gavrilova, C. J. Kenneth Tan. Editors: Yingxu Wang, Keith Chan [Архівовано 28 березня 2018 у Wayback Machine.] / Lecture Notes in Computer Science^[en] / Volume 5540, Springer Verlag, 2009

[13] Coset intersection problem [Архівовано 29 березня 2018 у Wayback Machine.] // The Group Properties Wiki [Архівовано 22 жовтня 2017 у Wayback Machine.] (beta)

[14] Complexity of the coset intersection problem [Архівовано 24 грудня 2015 у Wayback Machine.] // Theoretical Computer Science Stack Exchange
Graph Isomorphism Problem [Архівовано 29 березня 2018 у Wayback Machine.] // ibid.
Complexity of simple undirected graph isomorphism problem [Архівовано 29 березня 2018 у Wayback Machine.] // ibid.

[3]

[1]

[2]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Ласло Бабай
угор. Babai László

Народився	20 липня 1950(1950-07-20) (74 роки) Будапешт, Угорська Народна Республіка^[1]
Країна	Угорщина
Національність	угорець
Діяльність	математик, інформатик, викладач університету
Alma mater	Університет Лоранда Етвеша , Угорська академія наук
Галузь	математика
Заклад	Чиказький університет
Науковий керівник	Пал Туран і Віра Шош^[2]
Аспіранти, докторанти	Маріо Жегеді^d Gábor Tardos^d Carsten Lund^d^[2] Péter Hajnal^d^[2] Péter Pál Pálfy^d^[2] Barry Guiduli^d^[2] José Augusto Ramos Soares^d^[2] Tamás Lengyel^d^[2] Lajos Rónyai^d^[2] Albert J. Goodman^d^[2] Robert M. Beals^d^[2] Satyanarayana V. Lokam^d^[2] Peter Kimmel^d^[2] Daniel Štefankovič^d^[2] Evelin Toumpakari^d^[2] Samuel Kutin^d^[2] Thomas Hayes^d^[2] Katalin Friedl^d^[2] Murali Krishnan Ganapathy^d^[2] Aytek Erdil^d^[2] Sourav Chakraborty^d^[2] Paolo Codenotti^d^[2] Youming Qiao^d^[2] John Wilmes^d^[2]
Членство	Угорська академія наук Американська академія мистецтв і наук
Нагороди	Премія Геделя (1993) Премія Кнута (2015)
Особ. сторінка	László Babai
Ласло Бабай у Вікісховищі