Ласло Бабай - László Babai

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

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

Жизнь

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

Работа

Он автор более 180 научных работ.[1]Его заметные достижения включают введение интерактивные системы доказательства,[3] введение термина Алгоритм Лас-Вегаса,[4] и введение теоретико-групповой методы в изоморфизм графов тестирование.[4] В ноябре 2015 года он объявил квазиполиномиальное время алгоритм для проблема изоморфизма графов.[5][6]

Главный редактор рецензируемого интернет-журнала. Теория вычислений.[7] Бабай также участвовал в создании Будапештские семестры по математике программа и впервые придумал название.

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

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

Абстрактные

Мы показываем, что Проблема изоморфизма графов (GI) и связанные с этим проблемы изоморфизма струн[12] (при групповом действии) (SI) и Coset Intersection (CI)[13][14] можно решить в квазиполиномиальном время. Лучшая предыдущая граница для GI была куда - количество вершин (Luks, 1983); для двух других задач оценка была аналогичной, куда - размер области перестановки (Бабай, 1983).
Алгоритм основан на структуре SI Люкса и атакует конфигурации барьеров для алгоритма Люкса с помощью теоретико-групповых «локальных сертификатов» и методов комбинаторного канонического разделения. Мы показываем, что в четко определенном смысле Графики Джонсона являются единственными препятствиями на пути к эффективному каноническому разделению.

Почести

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

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

В 2015 году был избран[16] сотрудник Американская академия искусств и наук, и выиграл Приз Кнута.

Источники

копировать из Lenta.ru // texnomaniya.ru, 20 ноября 2015 г.
Опубліковано быстрый алгоритм для задачі изоморфізму графів // Джерело: Хабрахабр, перекладено 16 грудня 2015, 06:30

Рекомендации

  1. ^ а б c d е ж Биография Резюме с веб-сайта Бабая, получено 28 января 2016 г.
  2. ^ Ласло Бабай на Проект "Математическая генеалогия"
  3. ^ Бабай, Ласло; Моран, Шломо (1988), "Игры Артура-Мерлина: рандомизированная система доказательств и иерархия классов сложности", J. Comput. Syst. Sci., 36 (2): 254–276, Дои:10.1016/0022-0000(88)90028-1.
  4. ^ а б Бабай, Ласло (1979), Алгоритмы Монте-Карло в тестировании изоморфизма графов (PDF), Тех. Отчет, Université de Montréal.
  5. ^ Чо, Адриан (10 ноября 2015 г.), «Математик заявляет о прорыве в теории сложности», Наука, Дои:10.1126 / science.aad7416
  6. ^ а б Кларрайх, Эрика. «Знаковый алгоритм выходит из 30-летнего тупика». Quantamagazine.org. Журнал Quanta.
  7. ^ Теория вычислений редакторы, получено 30 июля 2010.
  8. ^ Большой результат об изоморфизме графов // 4 ноября 2015 г., Алгоритм быстрого изоморфизма графов // 11 ноября 2015 г.
  9. ^ Заявленный прорыв решает классическую вычислительную проблему // Обзор технологий MIT, Том Симоните, 13 ноября 2015 г.
  10. ^ Бабай, Ласло (2016), "Изоморфизм графов в квазиполиномиальном времени [расширенная аннотация]", Материалы сорок восьмого ежегодного симпозиума ACM по теории вычислений (STOC '16), Нью-Йорк, Нью-Йорк, США: ACM, стр. 684–697, arXiv:1512.03547, Дои:10.1145/2897518.2897542, ISBN  978-1-4503-4132-5
  11. ^ Ласло Бабай: Исправление дела UPCC по делу Split-or-Johnson, опубликовано 14 января 2017 г.
  12. ^ Определение 2.3. Изоморфизм струн, в: Транзакции по вычислительной науке V. Специальный выпуск о представлении когнитивных знаний. Главные редакторы: Гаврилова Марина Львовна, Кеннет Тан К. Редакторы: Инсю Ван, Кейт Чан / Конспект лекций по информатике / Том 5540, Springer Verlag, 2009
  13. ^ Проблема пересечения смежных классов // Вики Сообщества (бета)
  14. ^ Сложность проблемы пересечения смежных классов // Теоретический обмен стеком информатики, задано 25 сентября 2014 г. в 9:43
  15. ^ Премия Гёделя 1993 года В архиве 2015-12-08 в Wayback Machine, ACM SIGACT, получено 14 августа 2010.
  16. ^ Американская академия искусств и наук. Стипендиаты 2015 г. и их сотрудники

внешняя ссылка