Ласло Бабай (; , )Curriculum vitae // Babai's web site — угорський та американський математик, професор математики та інформатики (computer science) в Чиказькому університеті. Його дослідження зосереджені у галузях: теорія складності обчислень, теорія алгоритмів, комбінаторика, та скінченні групи, з наголосом на взаємодію між цими галузями. Автор понад 180 академічних праць.

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

Автор алгоритму Лас-Вегас (1979), версії методу Монте-Карло.Ласло Бабай, Monte-Carlo algorithms in graph isomorphism testing , Université de Montréal, D.M.S. No. 79-10.

Graph Isomorphism in Quasipolynomial Time

З 10 листопада по 1 грудня 2015 року на семінарі «Combinatorics and Theoretical Computer Science» в Чиказькому університеті зробив три доповіді «Graph Isomorphism in Quasipolynomial Time», у яких виклав алгоритм, який вирішує ізоморфізму графів за квазіполіноміальний час.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:00A Big Result On Graph Isomorphism // November 4, 2015, A Fast Graph Isomorphism Algorithm // November 11, 2015Combinatorics 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 10 грудня 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.

11 грудня 2015 у arXiv.org оприлюднено однойменну статтю «Graph Isomorphism in Quasipolynomial Time»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.

<big><big> We show that the Graph Isomorphism and the related problems of String IsomorphismDefinition 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 / / Volume 5540, Springer Verlag, 2009 (under group action) (SI) and Coset Intersection (CI)Coset intersection problem // The Group Properties Wiki (beta)Complexity of the coset intersection problem // Theoretical Computer Science Stack Exchange Graph Isomorphism Problem // ibid. Complexity of simple undirected graph isomorphism problem // ibid. can be solved in quasipolynomial time. The best previous bound for GI was where is the number of vertices (, 1983); for the other two problems, the bound was similar, where 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.</big></big>

Джерела

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

Див. також

Група чорної скриньки

Примітки