Ласло Бабай

Ласло Бабай (Шаблон:Lang-hu; Шаблон:ДН, Шаблон:Місце народження) — угорський та американський математик, професор математики та інформатики (computer science) в Чиказькому університеті. Його дослідження зосереджені у галузях: теорія складності обчислень, теорія алгоритмів, комбінаторика, та скінченні групи, з наголосом на взаємодію між цими галузями. Автор понад 180 академічних праць.

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

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

Graph Isomorphism in Quasipolynomial Time

З 10 листопада по 1 грудня 2015 року на семінарі «Combinatorics and Theoretical Computer Science» в Чиказькому університеті зробив три доповіді «Graph Isomorphism in Quasipolynomial Time», у яких виклав алгоритм, який вирішує Шаблон:Iw2 ізоморфізму графів за квазіполіноміальний $e^{\log (n{)}^{O(1)}}$ час. 10 грудня 2015 опубліковано відео першої доповіді.

11 грудня 2015 у arXiv.org оприлюднено однойменну статтю «Graph Isomorphism in Quasipolynomial Time». Шаблон:Приховати

We show that the Graph Isomorphism Шаблон:Iw2 and the related problems of String Isomorphism (under group action) (SI) and Coset Intersection (CI) can be solved in quasipolynomial

$\exp \left({(\log n)}^{O\left(1\right)}\right)$

time. The best previous bound for GI was

$\exp \left(O\left(\sqrt{n\log n}\right)\right),$

where

$n$

is the number of vertices (Шаблон:Iw2, 1983); for the other two problems, the bound was similar,

$\exp \left(\tilde{O}\left(\sqrt{n}\right)\right),$

where

$n$

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.

|}

Джерела

• 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 Шаблон:Webarchive, by Adrian Cho 10 November 2015 17:45 // Posted in Math Шаблон:Webarchive, Science AAAS News
• A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details Шаблон:Webarchive + Background on Graph Isomorphism + The Main Result // Math ∩ Programming. Posted on November 12, 2015 by j2kun
• Landmark Algorithm Breaks 30-Year Impasse Шаблон:Webarchive, Algorithm Solves Graph Isomorphism in Record Time // Quanta Magazine. By: Erica Klarreich, December 14, 2015
• A Little More on the Graph Isomorphism Algorithm Шаблон:Webarchive // November 21, 2015, by RJLipton+KWRegan (Ken Regan and Dick Lipton)
• [Ласло] Бабай приблизился к решению «проблемы тысячелетия» Шаблон:Webarchive // Наука Lenta.ru, 14:48, 20 ноября 2015

copy Шаблон:Webarchive from Lenta.ru // texnomaniya.ru, 20 ноября 2015

• Опубликован быстрый алгоритм для задачи изоморфизма графов Шаблон:Webarchive // Анатолий Ализар, Хабрахабр, 16 декабря в 02:12

Див. також

• Шаблон:Iw
• Група чорної скриньки