Ласло «Лачи» Бабай (родился 20 июля 1950 года в Будапеште ) [1] - венгерский профессор компьютерных наук и математики в Чикагском университете . Его исследования сосредоточены на теории сложности вычислений , алгоритмах , комбинаторике и конечных группах , с акцентом на взаимодействия между этими областями.
Ласло Бабай | |
---|---|
Родившийся | |
Национальность | венгерский язык |
Альма-матер | Венгерская Академия Наук |
Награды | Премия Гёделя (1993) Премия Кнута (2015) Премия Дейкстры (2016) |
Научная карьера | |
Поля | Компьютерные науки , математика |
Учреждения | Чикагский университет |
Докторант | Пал Туран Вера Т. Сос |
Докторанты | Марио Сегеди Габор Тардос |
Жизнь
В 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]
Он является главным редактором рецензируемого онлайн-журнала Theory of Computing . [7] Бабай также участвовал в создании программы « Будапештские семестры по математике » и первым придумал это название.
Изоморфизм графов за квазиполиномиальное время
После объявления результата в 2015 году [6] [8] [9] Бабай представил документ, доказывающий, что проблема изоморфизма графов может быть решена за квазиполиномиальное время в 2016 году на симпозиуме ACM по теории вычислений . [10] В ответ на ошибку, обнаруженную Харальдом Хельфготтом , он опубликовал обновление в 2017 году. [11]
Мы показываем, что проблема изоморфизма графов (GI) и связанные с ней проблемы изоморфизма строк [12] (при групповом действии) (SI) и пересечения смежных классов (CI) [13] [14] могут быть решены в квазиполиномиальномвремя. Лучшая предыдущая граница для GI была где - количество вершин ( Лукс , 1983); для двух других задач оценка была аналогичной, где - размер области перестановки (Бабай, 1983).
Алгоритм основан на структуре SI Люкса и атакует барьерные конфигурации для алгоритма Люкса с помощью теоретико-групповых «локальных сертификатов» и методов комбинаторного канонического разделения. Мы показываем, что в строго определенном смысле графы Джонсона являются единственными препятствиями на пути к эффективному каноническому разбиению.
Почести
В 1988 г. Бабай получил Государственную премию Венгрии, в 1990 г. он был избран членом-корреспондентом Венгерской академии наук, а в 1994 г. стал ее действительным членом. [1] В 1999 г. Будапештский технологический и экономический университет присвоил ему звание почетного доктора. [1]
В 1993 году Бабай был удостоен премии Геделя вместе с Шафи Гольдвассером , Сильвио Микали , Шломо Мораном и Чарльзом Ракоффом за их работы по интерактивным системам доказательства. [15]
В 2015 году он был избран [16] членом Американской академии искусств и наук и получил премию Кнута .
Бабай был приглашенным докладчиком на Международных конгрессах математиков в Киото (1990 г.), Цюрихе (1994 г., пленарное выступление) и Рио-де-Жанейро (2018 г.).
Источники
- Алгоритм профессора Ласло Бабая - следующий большой шаг в преодолении изоморфизма в графах // Опубликовано 20 ноября 2015 г. Отделение физических наук / Чикагский университет
- Математик заявляет о прорыве в теории сложности , Адриан Чо 10 ноября 2015 г. 17:45 // Posted in Math , Science AAAS News
- Алгоритм квазиполиномиального времени для изоморфизма графов: детали + справочная информация об изоморфизме графов + основной результат // Math ∩ Programming. Опубликовано 12 ноября 2015 г. автором j2kun
- Знаковый алгоритм выходит из 30-летнего тупика , алгоритм решает изоморфизм графов в рекордно короткие сроки // Quanta Magazine. Автор: Эрика Кларрайх, 14 декабря 2015 г.
- Еще немного об алгоритме изоморфизма графов // 21 ноября 2015 г., RJLipton + KWRegan (Ken Regan and Dick Lipton)
- [Ласло] Бабай приблизился к решению «проблемы тысячелетия» // Наука Lenta.ru, 14:48, 20 ноября 2015
- копия с сайта Lenta.ru // texnomaniya.ru, 20 ноября 2015 г.
- Опубликован быстрый алгоритм для задач изоморфизма графов // Анатолий Ализар, Хабрахабр, 16 декабря в 02:12
- Опубліковано швидкий алгоритм для задачі изоморфізму графів // Джерело: Хабрахабр, перекладено 16 грудня 2015, 06:30
Рекомендации
- ^ a b c d e f Curriculum vitae с веб-сайта Бабая, получено 28 января 2016 г.
- ↑ Ласло Бабай в проекте « Математическая генеалогия»
- ^ Бабай, Ласло; Моран, Шломо (1988), "Игры Артура-Мерлина: рандомизированная система доказательств и иерархия классов сложности", J. Comput. Syst. Sci. , 36 (2): 254-276, DOI : 10,1016 / 0022-0000 (88) 90028-1.
- ^ а б Бабай, Ласло (1979), Алгоритмы Монте-Карло в тестировании изоморфизма графов (PDF) , Tech. Отчет, Университет Монреаля.
- ^ Чо, Адриан (10 ноября 2015 г.), «Математик заявляет о прорыве в теории сложности», Science , doi : 10.1126 / science.aad7416
- ^ а б Кларрайх, Эрика. «Знаковый алгоритм выходит из 30-летнего тупика» . Quantamagazine.org . Журнал Quanta .
- ^ Theory of Computing editors , получено 30 июля 2010 г.
- ^ Большой результат по изоморфизму графов // 4 ноября 2015 г., алгоритм быстрого изоморфизма графов // 11 ноября 2015 г.
- ^ Заявленный прорыв решает классическую вычислительную проблему // Обзор технологий Массачусетского технологического института, Том Симоните, 13 ноября 2015 г.
- ^ Бабай, Ласло (2016), «Изоморфизм графов в квазиполиномиальном времени [Расширенная аннотация]», Труды сорок восьмого ежегодного симпозиума ACM по теории вычислений (STOC '16) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 684 –697, arXiv : 1512.03547 , doi : 10.1145 / 2897518.2897542 , ISBN 978-1-4503-4132-5
- ^ Ласло Бабаи: Крепление дела УПККА сплит-или-Джонсон , размещенное на 14 января 2017
- ^ Определение 2.3. Строка Изоморфизм в: Труды по вычислительной науке V . Специальный выпуск о представлении когнитивных знаний. Главные редакторы: Гаврилова Марина Львовна, CJ Kenneth Tan. Редакторы: Yingxu Wang, Keith Chan / Lecture Notes in Computer Science / Volume 5540, Springer Verlag , 2009.
- ^ Проблема пересечения смежных классов // The Group Properties Wiki (бета)
- ^ Сложность проблемы пересечения смежных классов // Теоретический обмен стеком информатики, задано 25 сентября 2014 г. в 9:43
- ^ 1993 Гедель премии архивации 2015-12-08 в Wayback Machine , ACM SIGACT , извлекаются 2010-08-14.
- ^ Американская академия искусств и наук . Стипендиаты 2015 г. и их сотрудники
Внешние ссылки
- СМИ, связанные с Ласло Бабаем на Викискладе?
- Персональный сайт .
- MathSciNet: «Статьи, написанные Бабаем, Ласло». [ постоянная мертвая ссылка ]
- DBLP: Ласло Бабай .