Ласло Бабай

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Ласло Бабай
угор. Babai László
Laszlo Babai.jpg
Народився 20 липня 1950(1950-07-20) (67 років)
Будапешт
Громадянство
(підданство)
Угорщина
Національність угорець
Alma mater Університет Лоранда Етвеша ,
Угорська академія наук
Галузь наукових інтересів математика
Заклад Чиказький університет
Науковий керівник Pál Turán[d]
Нагороди Премія Геделя (1993)
Премія Кнута (2015)
Особ. сторінка László Babai


CMNS: Ласло Бабай на Вікісховищі

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

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

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

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

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

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

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

copy from Lenta.ru // texnomaniya.ru, 20 ноября 2015
Опубліковано швидкий алгоритм для задачі ізоморфізму графів // Джерело: Хабрахабр, перекладено 16 грудня 2015, 06:30

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

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

  1. а б в Curriculum vitae // Babai's web site
  2. Ласло Бабай(англ.) в проекті «Математична генеалогія».
  3. Ласло Бабай, Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D.M.S. No. 79-10.
  4. 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
  5. A Big Result On Graph Isomorphism // November 4, 2015, A Fast Graph Isomorphism Algorithm // November 11, 2015
  6. Combinatorics 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)
  7. Claimed Breakthrough Slays Classic Computing Problem // MIT Technology Review, by Tom Simonite on November 13, 2015
  8. 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
  9. 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
  10. 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
  11. Coset intersection problem // The Group Properties Wiki (beta)
  12. Complexity of the coset intersection problem // Theoretical Computer Science Stack Exchange
    Graph Isomorphism Problem // ibid.
    Complexity of simple undirected graph isomorphism problem // ibid.