Ласло Бабай

угорський математик та інформатик

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

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

Бабай вивчав математику в Будапештському університеті імені Лоранда Етвеша з 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] ізоморфізму графів за квазіполіноміальний   час.[6][7][8][9] 10 грудня 2015 опубліковано відео першої доповіді[10].

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

Джерела

ред.
copy [Архівовано 4 березня 2016 у Wayback Machine.] from Lenta.ru // texnomaniya.ru, 20 ноября 2015

Див. також

ред.

Примітки

ред.
  1. http://news.uchicago.edu/profile/laszlo-babai
  2. а б в г д е ж и к л м н п р с т у ф х ц ш щ ю Математичний генеалогічний проєкт — 1997.
  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.