Ласло Бабай
Ласло Бабай | |
---|---|
угор. László Babai | |
![]() | |
Народився | 20 липня 1950 (74 роки) Будапешт |
Країна | ![]() |
Національність | угорець |
Діяльність | математик, інформатик, викладач університету |
Alma mater | Університет Лоранда Етвеша , Угорська академія наук |
Галузь | математика |
Заклад | Чиказький університет |
Науковий керівник | Пал Туран і Віра Шош[1] |
Аспіранти, докторанти | Маріо Жегедіd Gábor Tardosd Carsten Lundd[1] Péter Hajnald[1] Péter Pál Pálfyd[1] Barry Guidulid[1] José Augusto Ramos Soaresd[1] Tamás Lengyeld[1] Lajos Rónyaid[1] Albert J. Goodmand[1] Robert M. Bealsd[1] Satyanarayana V. Lokamd[1] Peter Kimmeld[1] Daniel Štefankovičd[1] Evelin Toumpakarid[1] Samuel Kutind[1] Thomas Hayesd[1] Katalin Friedld[1] Murali Krishnan Ganapathyd[1] Aytek Erdild[1] Sourav Chakrabortyd[1] Paolo Codenottid[1] Youming Qiaod[1] John Wilmesd[1] |
Членство | Угорська академія наук Американська академія мистецтв і наук |
Нагороди | Премія Геделя (1993) Премія Кнута (2015) |
Особ. сторінка | László Babai |
![]() |
Ласло Бабай, угор. László Babai (20 липня 1950, Будапешт)[2] — угорський професор математики та інформатики (computer science) в Чиказькому університеті. Його дослідження зосереджені у галузях: теорія складності обчислень, теорія алгоритмів, комбінаторика, та скінченні групи[en], з наголосом на взаємодію між цими галузями. Автор понад 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] ізоморфізма графів за квазіполіноміальний (exp(polylog n)) час.[5][6][7][8] 10 грудня 2015 опубліковано відео першої доповіді[9].
11 грудня 2015 у arXiv.org оприлюднено однойменну статтю «Graph Isomorphism in Quasipolynomial Time»[10].
abstract |
---|
|
Джерела
- 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, by Adrian Cho 10 November 2015 17:45 // Posted in Math, Science AAAS News
- A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details + Background on Graph Isomorphism + The Main Result // Math ∩ Programming. Posted on November 12, 2015 by j2kun
- Landmark Algorithm Breaks 30-Year Impasse, Algorithm Solves Graph Isomorphism in Record Time // Quanta Magazine. By: Erica Klarreich, December 14, 2015
- A Little More on the Graph Isomorphism Algorithm // November 21, 2015, by RJLipton+KWRegan (Ken Regan and Dick Lipton)
- [Ласло] Бабай приблизился к решению «проблемы тысячелетия» // Наука Lenta.ru, 14:48, 20 ноября 2015
- copy from Lenta.ru // texnomaniya.ru, 20 ноября 2015
- Опубликован быстрый алгоритм для задачи изоморфизма графов // Анатолий Ализар, Хабрахабр, 16 декабря в 02:12
- Опубліковано швидкий алгоритм для задачі ізоморфізму графів // Джерело: Хабрахабр, перекладено 16 грудня 2015, 06:30
Примітки
- ↑ а б в г д е ж и к л м н п р с т у ф х ц ш щ ю Математичний генеалогічний проєкт — 1997.
- ↑ а б в Curriculum vitae // Babai's web site
- ↑ Ласло Бабай(англ.) у проєкті «Математична генеалогія».
- ↑ Ласло Бабай, Monte-Carlo algorithms in graph isomorphism testing, 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 // November 4, 2015, A Fast Graph Isomorphism Algorithm // November 11, 2015
- ↑ 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)
- ↑ Claimed Breakthrough Slays Classic Computing Problem // MIT Technology Review, by Tom Simonite on November 13, 2015
- ↑ 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
- ↑ 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
- ↑ 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
- ↑ Coset intersection problem // The Group Properties Wiki (beta)
- ↑ Complexity of the coset intersection problem // Theoretical Computer Science Stack Exchange, asked Sep 25 2014 at 9:43