Ласло Бабай

Ласло Бабай
Ласло Бабай
	Бабай в Обервольфахе в 2011 году.
Рожденный	20 июля 1950 г. (74 года) ; Будапешт , Венгрия
Национальность	венгерский
Альма-матер	Венгерская академия наук
Награды	Премия Гёделя (1993). ; Премия Кнута (2015) ; Премия Дейкстры (2016)
	Научная карьера
Поля	Информатика , Математика
Учреждения	Чикагский университет
Докторантура	Пал Туран ; Вера Т. Одна
Докторанты	Марио Сегеди ; Габор Тардос ; Петер Пал Палфи

Ласло «Лачи» Бабай (родился 20 июля 1950 года в Будапеште ) ^{[ 1 ]} — венгерский профессор информатики и математики Чикагского университета . Его исследования сосредоточены на теории сложности вычислений , алгоритмах , комбинаторике и конечных группах , с упором на взаимодействие между этими областями.

Жизнь

В 1968 году Бабай завоевал золотую медаль на Международной математической олимпиаде . Бабай изучал математику на факультете естественных наук Университета Этвеша Лоранда с 1968 по 1973 год, получил степень доктора философии Венгерской академии наук в 1975 году и степень доктора наук Венгерской академии наук в 1984 году. ^{[ 1 ]}^{[ 2 ]} С 1971 года он занимал должность преподавателя в Университете Этвеша Лоранда; в 1987 году он занял совместные должности профессора алгебры в Этвёше Лоранде и информатики в Чикагском университете. В 1995 году он начал работать на математическом факультете в Чикаго и оставил свою должность в Eötvös Loránd. ^{[ 1 ]}

Работа

Он является автором более 180 научных работ. ^{[ 1 ]} Среди его заметных достижений — внедрение интерактивных систем доказательств . ^{[ 3 ]} введение термина «алгоритм Лас-Вегаса» , ^{[ 4 ]} и внедрение теоретико-групповых методов при проверке изоморфизма графов . ^{[ 4 ]} В ноябре 2015 года он анонсировал алгоритм квазиполиномиального времени для решения проблемы изоморфизма графов . ^{[ 5 ]}^{[ 6 ]}

Он является главным редактором рецензируемого онлайн-журнала Theory of Computing . ^{[ 7 ]} Бабай также участвовал в создании программы «Будапештские семестры по математике» и первым придумал это название.

Изоморфизм графов за квазиполиномиальное время

После объявления результатов в 2015 году ^{[ 6 ]}^{[ 8 ]}^{[ 9 ]} Бабай представил статью, доказывающую, что проблема изоморфизма графов может быть решена за квазиполиномиальное время. в 2016 году на симпозиуме ACM по теории вычислений . ^{[ 10 ]} В ответ на ошибку, обнаруженную Харальдом Хелфготтом , он опубликовал обновление в 2017 году. ^{[ 11 ]}

абстрактный

We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism^[12] (under group action) (SI) and Coset Intersection (CI)^[13]^[14] 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, 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 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.

Почести

В 1988 году Бабай стал лауреатом Государственной премии Венгрии, в 1990 году его избрали членом-корреспондентом Венгерской академии наук, а в 1994 году он стал её действительным членом. ^{[ 1 ]} В 1999 году Будапештский университет технологии и экономики присвоил ему звание почетного доктора. ^{[ 1 ]}

В 1993 году Бабай был удостоен премии Гёделя вместе с Шафи Гольдвассером , Сильвио Микали , Шломо Мораном и Чарльзом Ракоффом за их работы по системам интерактивных доказательств. ^{[ 15 ]}

В 2015 году он был избран ^{[ 16 ]} член Американской академии искусств и наук , лауреат премии Кнута .

Бабай был приглашенным докладчиком на Международных конгрессах математиков в Киото (1990 г.), Цюрихе (1994 г., пленарный доклад) и Рио-де-Жанейро (2018 г.).

Источники

Алгоритм профессора Ласло Бабая — следующий большой шаг в преодолении изоморфизма в графах // Опубликовано 20 ноября 2015 г. Отделение физических наук / Чикагский университет
Математик заявляет о прорыве в теории сложности , Адриан Чо 10 ноября 2015 г. 17:45 // Опубликовано в рубрике: Математика , Наука AAAS News
Квазиполиномиальный алгоритм определения изоморфизма графов: подробности + предыстория изоморфизма графов + основной результат // Math ∩ Programming. Опубликовано 12 ноября 2015 г. автором j2kun
Еще немного об алгоритме изоморфизма графов // 21 ноября 2015 г., автор RJLipton+KWRegan (Кен Риган и Дик Липтон)

copy from Lenta.ru // texnomaniya.ru, 20 ноября 2015

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

Опубликован быстрый алгоритм задачи изоморфизма графов Archived 2017-07-03 at the Wayback Machine // Источник: Хабрахабр, переведен 16 декабря 2015, 06:30

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Биографические данные с веб-сайта Бабая, получены 28 января 2016 г.
^ Ласло Бабай в проекте «Математическая генеалогия»
^ Бабай, Ласло; Моран, Шломо (1988), «Игры Артура-Мерлина: рандомизированная система доказательств и иерархия классов сложности», J. Comput. Сист. наук. , 36 (2): 254–276, doi : 10.1016/0022-0000(88)90028-1 .
^ Jump up to: ^а ^б Бабай, Ласло (1979), Алгоритмы Монте-Карло для проверки изоморфизма графов (PDF) , Tech. Отчет, Университет Монреаля .
^ Чо, Адриан (10 ноября 2015 г.), «Математик заявляет о прорыве в теории сложности», Science , doi : 10.1126/science.aad7416
^ Jump up to: ^а ^б Кларрайх, Эрика (14 декабря 2015 г.). «Алгоритм ориентира выходит из 30-летнего тупика» . Журнал Кванта . Архивировано из оригинала 21 января 2016 г.
^ Theory of Computing Редакция , получено 30 июля 2010 г.
^ Большой результат по изоморфизму графов // 4 ноября 2015 г., Алгоритм быстрого изоморфизма графов // 11 ноября 2015 г.
↑ Заявленный прорыв решает классическую вычислительную проблему. Архивировано 22 января 2016 г. в Wayback Machine // Обзор технологий MIT, Том Симонайт, 13 ноября 2015 г.
^ Бабай, Ласло (2016), «Изоморфизм графов в квазиполиномиальное время [расширенное резюме]», Труды сорок восьмого ежегодного симпозиума ACM по теории вычислений (STOC '16) , Нью-Йорк, штат Нью-Йорк, США: ACM, стр. 684 –697, arXiv : 1512.03547 , дои : 10.1145/2897518.2897542 , ISBN 978-1-4503-4132-5 , S2CID 17118954
↑ Ласло Бабай: Исправление дела UPCC о Сплит-или-Джонсоне , опубликовано 14 января 2017 г.
^ Определение 2.3. Строковый изоморфизм , в: Труды по вычислительной технике V. Специальный выпуск о представлении когнитивных знаний . Главные редакторы: Марина Л. Гаврилова , Си Джей Кеннет Тан. Редакторы: Инсюй Ван, Кейт Чан] / Конспекты лекций по информатике / Том 5540, Springer Verlag , 2009 г.
^ Проблема пересечения смежных классов // The Group Properties Wiki (бета)
^ Сложность проблемы пересечения смежных классов // Theoretical Computer Science Stack Exchange, вопрос задан 25 сентября 2014 г., 9:43
^ Премия Гёделя 1993 г. Архивировано 8 декабря 2015 г. в Wayback Machine , ACM SIGACT , получено 14 августа 2010 г.
^ Американская академия искусств и наук . Стипендиаты 2015 года и их принадлежность

Внешние ссылки

[cv-1] Jump up to: ^а ^б ^с ^д ^и ^ж Биографические данные с веб-сайта Бабая, получены 28 января 2016 г.

[2] Ласло Бабай в проекте «Математическая генеалогия»

[3] Бабай, Ласло; Моран, Шломо (1988), «Игры Артура-Мерлина: рандомизированная система доказательств и иерархия классов сложности», J. Comput. Сист. наук. , 36 (2): 254–276, doi : 10.1016/0022-0000(88)90028-1 .

[lv79-4] Jump up to: ^а ^б Бабай, Ласло (1979), Алгоритмы Монте-Карло для проверки изоморфизма графов (PDF) , Tech. Отчет, Университет Монреаля .

[5] Чо, Адриан (10 ноября 2015 г.), «Математик заявляет о прорыве в теории сложности», Science , doi : 10.1126/science.aad7416

[quanta-6] Jump up to: ^а ^б Кларрайх, Эрика (14 декабря 2015 г.). «Алгоритм ориентира выходит из 30-летнего тупика» . Журнал Кванта . Архивировано из оригинала 21 января 2016 г.

[7] Theory of Computing Редакция , получено 30 июля 2010 г.

[8] Большой результат по изоморфизму графов // 4 ноября 2015 г., Алгоритм быстрого изоморфизма графов // 11 ноября 2015 г.

[9] Заявленный прорыв решает классическую вычислительную проблему. Архивировано 22 января 2016 г. в Wayback Machine // Обзор технологий MIT, Том Симонайт, 13 ноября 2015 г.

[10] Бабай, Ласло (2016), «Изоморфизм графов в квазиполиномиальное время [расширенное резюме]», Труды сорок восьмого ежегодного симпозиума ACM по теории вычислений (STOC '16) , Нью-Йорк, штат Нью-Йорк, США: ACM, стр. 684 –697, arXiv : 1512.03547 , дои : 10.1145/2897518.2897542 , ISBN 978-1-4503-4132-5 , S2CID 17118954

[11] Ласло Бабай: Исправление дела UPCC о Сплит-или-Джонсоне , опубликовано 14 января 2017 г.

[12] Определение 2.3. Строковый изоморфизм , в: Труды по вычислительной технике V. Специальный выпуск о представлении когнитивных знаний . Главные редакторы: Марина Л. Гаврилова , Си Джей Кеннет Тан. Редакторы: Инсюй Ван, Кейт Чан] / Конспекты лекций по информатике / Том 5540, Springer Verlag , 2009 г.

[13] Проблема пересечения смежных классов // The Group Properties Wiki (бета)

[14] Сложность проблемы пересечения смежных классов // Theoretical Computer Science Stack Exchange, вопрос задан 25 сентября 2014 г., 9:43

[15] Премия Гёделя 1993 г. Архивировано 8 декабря 2015 г. в Wayback Machine , ACM SIGACT , получено 14 августа 2010 г.

[16] Американская академия искусств и наук . Стипендиаты 2015 года и их принадлежность

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[12]

[13]

[14]

[ 15 ]

[ 16 ]

v т и премии Гёделя Лауреаты
1990s	Babai / Goldwasser / Micali / Moran / Rackoff (1993) Håstad (1994) Immerman / Szelepcsényi (1995) Jerrum / Sinclair (1996) Halpern / Moses (1997) Toda (1998) Shor (1999)
2000s	Vardi / Wolper (2000) Arora / Feige / Goldwasser / Lund / Lovász / Motwani / Safra / Sudan / Szegedy (2001) Sénizergues (2002) Freund / Schapire (2003) Herlihy / Saks / Shavit / Zaharoglou (2004) Alon / Matias / Szegedy (2005) Agrawal / Kayal / Saxena (2006) Razborov / Rudich (2007) Teng / Spielman (2008) Reingold / Vadhan / Wigderson (2009)
2010s	Arora / Mitchell (2010) Håstad (2011) Koutsoupias / Papadimitriou / Roughgarden / É. Tardos / Nisan / Ronen (2012) Boneh / Franklin / Joux (2013) Fagin / Lotem / Naor (2014) Spielman / Teng (2015) Brookes / O'Hearn (2016) Dwork / McSherry / Nissim / Smith (2017) Regev (2018) Dinur (2019)
2020s	Moser / G. Tardos (2020) Bulatov / Cai / Chen / Dyer / Richerby (2021) Brakerski / Gentry / Vaikuntanathan (2022)

v т и премии Кнута Лауреаты
1990s	Yao (1996) Valiant (1997) Lovász (1999)
2000s	Ullman (2000) Papadimitriou (2002) Ajtai (2003) Yannakakis (2005) Lynch (2007) Strassen (2008)
2010s	Johnson (2010) Kannan (2011) Levin (2012) Miller (2013) Lipton (2014) Babai (2015) Nisan (2016) Goldreich (2017) Håstad (2018) Wigderson (2019)
2020s	Dwork (2020) Vardi (2021) Alon (2022)

Базы данных авторитетного контроля
International	ISNI VIAF WorldCat
National	Germany Israel
Academics	Association for Computing Machinery DBLP Google Scholar MathSciNet Mathematics Genealogy Project zbMATH