Миклош Айтай (родился 2 июля 1946 года) - ученый-компьютерщик в Исследовательском центре IBM в Алмадене , США. В 2003 году он получил премию Кнута за его многочисленные вклады в эту область, включая классический алгоритм сортировочной сети (разработанный совместно с Дж. Комлосом и Эндре Семереди ), экспоненциальные нижние границы, суперлинейные пространственно-временные компромиссы для программ ветвления и другие уникальные и впечатляющие »результаты.
Миклош Айтаи | |
---|---|
Родившийся | |
Национальность | Венгерско-американский |
Альма-матер | Венгерская Академия Наук |
Награды | Премия Кнута (2003) [1] |
Научная карьера | |
Поля | Теория вычислительной сложности |
Учреждения | Исследовательский центр IBM Almaden |
Избранные результаты
Одно из состояний результатов Ajtai, что длина доказательства в логике высказываний по принципу Дирихле для п элементов растет быстрее , чем любой полином в п . Он также доказал, что утверждение «любые две счетные структуры , эквивалентные второму порядку, также изоморфны » согласовано с ZFC и не зависит от него . Аджтай и Семереди доказали теорему об углах , важный шаг к многомерным обобщениям теоремы Семереди . Вместе с Комлошем и Семереди он доказал верхнюю границу ct 2 / log t для числа Рамсея R (3, t ). Соответствующая нижняя граница была доказана Кимом только в 1995 году, за что ему была присуждена премия Фулкерсона . С Chvátal , новорожденным и Семередите , Ajtai доказал число неравенства пересечения , что любой рисунок графа с п вершинами и т ребрами, где т > 4 п , имеет , по меньшей мере , м 3 /100 л 2 пересечения . Аджтай и Дворк разработали в 1997 году криптосистему с открытым ключом на основе решеток ; Аджтай проделал большую работу над проблемами решетки . За его многочисленные вклады в теоретическую информатику он получил премию Кнута. [1]
Биоданные
В 1976 году Аджтай получил степень кандидата наук Венгерской академии наук . [2] С 1995 года он был внешним членом Венгерской академии наук .
В 1998 г. он был приглашенным спикером Международного конгресса математиков в Берлине. [3] В 2012 году он был избран членом Американской ассоциации развития науки . [4] В 2021 году он был избран членом Национальной академии наук. [5]
Библиография
- Айтай, Миклош: Оптимальные нижние границы параметров Коркина-Золотарева решетки и для алгоритма Шнорра для кратчайшей векторной задачи, в: Theory of Computering, Vol. 4, стр. 21-51. [6]
- Айтай, Миклош: Нижняя граница нелинейного времени для булевых ветвящихся программ, в: Теория компьютеризации, т. 1. С. 149-176. [6]
- Айтаи, Миклош: Создание сложных экземпляров решеточных задач. Электронный коллоквиум по завершенности вычислений, стр. 1-29. [7]
Избранные статьи
- Ajtai, М. (1979), "Изоморфизм и более высокого порядка эквивалентности", Анналы математической логики , 16 (3): 181-203, DOI : 10,1016 / 0003-4843 (79) 90001-9.
- Ajtai, M .; Komlós, J .; Семереди, Е. (1982), "Самая большая случайная составляющая K -куба", Combinatorica , 2 (1): 1-7, DOI : 10.1007 / BF02579276.
Рекомендации
- ^ а б http://www.sigact.org/Prizes/Knuth/2003.html
- ↑ Magyar Tudományos Akadémia, Альманах, 1986, Будапешт.
- ^ Айтай, Миклош (1998). «Сложность наихудшего случая, сложность в среднем и решеточные задачи» . Док. Математика. (Билефельд) Extra Vol. ICM Berlin, 1998, т. III . С. 421–428.
- ^ AAAS членов , избираемых в качестве стипендиатов , AAAS, 29 ноября 2012
- ^ «Национальная академия наук избирает новых членов, в том числе рекордное количество женщин, и международных членов» . nasonline.org . 26 апреля 2021 . Проверено 28 апреля 2021 года .
- ^ а б «Статьи Миклоша Айтая» . Теория вычислений . Проверено 23 октября 2019 года .
- ^ «Создание жестких экземпляров решетчатых задач» (PDF) . semanticscholar.org. Архивировано из оригинального (PDF) 9 марта 2019 года . Проверено 23 октября 2019 года .
Внешние ссылки
- Домашняя страница Миклоша Айтая
- Список публикаций от Microsoft Academic
- Миклош Айтай на проекте « Математическая генеалогия»