WikiSort.ru - Не сортированное

Ласло Бабаи
Ласло Бабаи
Дата рождения	20 июля 1950 (68 лет)
Место рождения	Будапешт, Венгрия[1];
Страна	Венгрия;
Научная сфера	комбинаторика
Место работы	Чикагский университет;
Альма-матер	Будапештский университет (1973);
Научный руководитель	Туран, Пал
Награды и премии	Премия Гёделя (1993) премия Кнута (2015) член Американской академии искусств и наук[d]
Сайт	people.cs.uchicago.edu/~…
	Ласло Бабаи на Викискладе

ПОИСК ПО САЙТУ | о проекте

Ласло Бабаи (венг. Babai László; род. 20 июля 1950 (1950-07-20), Будапешт)^[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] изоморфизма графов за квазиполиномиальный $\exp \left(P\left(\log(n)\right)\right)$ период времени, где $\displaystyle n\ -$ количество вершин, $P\left(\log(n)\right)\ -$ многочлен от $\log(n)$ .^[5]^[6]^[7]^[8]

10 декабря 2015 опубликовано видео первого доклада^[9].

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

abstract

We show that the Graph Isomorphism (GI) problem^[en] and the related problems of String Isomorphism^[11] (under action group) (SI) and Coset Intersection (CI)^[12]^[13] can be solved in quasipolynomial
$\exp \left(\left(\log n\right)^{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 (Luks^[en], 1983); for the other two problems, the bound was similar,
$\quad \qquad \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 group by theoretic «local certificates and combinatorial canonical partitioning techniques. We show that in a well-defined sense, Johnson graphs^[uk] are the only obstructions to effective canonical partitioning.

См. также

List of unsolved problems in computer science

Примечания

↑ http://news.uchicago.edu/profile/laszlo-babai
1 2 3 Curriculum vitae Архивировано 11 февраля 2014 года. // Babai’s web site
↑ Бабаи, Ласло (англ.) в проекте «Математическая генеалогия»
↑ «'Ласло Бабаи»', Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D. M. S. № 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 Архивировано 22 декабря 2015 года. 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, lecture seminar 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. Гаврилова, 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
Graph Isomorphism Problem // ibid.
Complexity of simple undirected graph isomorphism problem // ibid.

Ссылки

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

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии

[_2c79634af4bc3d1c-1] ttp://news.uchicago.edu/profile/laszlo-babai

[cv-2] 1 2 3 Curriculum vitae Архивировано 11 февраля 2014 года. // Babai’s web site

[3] Бабаи, Ласло (англ.) в проекте «Математическая генеалогия»

[4] «'Ласло Бабаи»', Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D. M. S. № 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 декабря 2015 года. 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, lecture seminar 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. Гаврилова, 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.

Тематические сайты	Математическая генеалогия · Zentralblatt MATH database
Нормативный контроль	GND: 170302806 · ISNI: 0000 0000 7960 5774 · VIAF: 121373888 · WorldCat Identities (via VIAF): 121373888

Ласло Бабаи

Дата рождения	20 июля 1950(1950-07-20) (68 лет)
Место рождения	Будапешт, Венгрия^[1]
Страна	Венгрия
Научная сфера	комбинаторика
Место работы	Чикагский университет
Альма-матер	Будапештский университет (1973)
Научный руководитель	Туран, Пал
Награды и премии	Премия Гёделя (1993) премия Кнута (2015) член Американской академии искусств и наук^[d]
Сайт	people.cs.uchicago.edu/~…
Ласло Бабаи на Викискладе