Ласло Бабай

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Ласло Бабай
угор. Babai László
Laszlo Babai.jpg
Народився 20 липня 1950(1950-07-20) (68 років)
Будапешт, Угорщина[1]
Громадянство
(підданство)
Flag of Hungary.svg Угорщина
Національність угорець
Діяльність математик, інформатик, викладач університету
Alma mater Університет Лоранда Етвеша ,
Угорська академія наук
Сфера інтересів математика
Заклад Чиказький університет
Науковий керівник Pál Turán[d]
Аспіранти, докторанти Mario Szegedy[d] і Gábor Tardos[d]
Член Угорська академія наук і Американська академія мистецтв і наук
Нагороди Премія Геделя (1993)
Премія Кнута (2015)
Особ. сторінка László Babai

Ласло Бабай у Вікісховищі?

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

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

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

Graph Isomorphism in Quasipolynomial Time[ред. | ред. код]

З 10 листопада по 1 грудня 2015 року на семінарі «Combinatorics and Theoretical Computer Science» в Чиказькому університеті зробив три доповіді «Graph Isomorphism in Quasipolynomial Time», у яких виклав алгоритм, який вирішує проблему[en] ізоморфізму графів за квазіполіноміальний час.[5][6][7][8] 10 грудня 2015 опубліковано відео першої доповіді[9].

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

Джерела[ред. | ред. код]

copy from Lenta.ru // texnomaniya.ru, 20 ноября 2015

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. http://news.uchicago.edu/profile/laszlo-babai
  2. а б в Curriculum vitae Архівовано 11 February 2014[Дата не збігається] у Wayback Machine. // Babai's web site
  3. Ласло Бабай(англ.) в проекті «Математична генеалогія».
  4. Ласло Бабай, Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D.M.S. No. 79-10.
  5. 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
  6. A Big Result On Graph Isomorphism // November 4, 2015, A Fast Graph Isomorphism Algorithm // November 11, 2015
  7. Combinatorics and Theoretical Computer Science Архівовано 22 December 2015[Дата не збігається] у Wayback Machine. 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)
  8. Claimed Breakthrough Slays Classic Computing Problem // MIT Technology Review, by Tom Simonite on November 13, 2015
  9. Graph Isomorphism in Quasipolynomial Time I, seminar lecture by László Babai on November 10, 2015. The University of Chicago // youtube, 1 год. 40 хв. Опубліковано 10 грудня 2015
  10. 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
  11. Definition 2.3. String Isomorphism // Google Books, in: Transactions on Computational Science V. Special Issue on Cognitive Knowledge Representation. Editors-in-Chief: Marina L. Gavrilova, C. J. Kenneth Tan. Editors: Yingxu Wang, Keith Chan / Lecture Notes in Computer Science[en] / Volume 5540, Springer Verlag, 2009
  12. Coset intersection problem // The Group Properties Wiki (beta)
  13. Complexity of the coset intersection problem // Theoretical Computer Science Stack Exchange
    Graph Isomorphism Problem // ibid.
    Complexity of simple undirected graph isomorphism problem // ibid.