Миклош Айтай | |
---|---|
Родился | (1946-07-02) 2 июля 1946 (возраст 74). Будапешт, Вторая Венгерская Республика |
Национальность | венгерско-американец |
Alma mater | Венгерская академия наук |
Награды | Премия Кнута (2003) |
Научная карьера | |
Области | Теория вычислительной сложности |
Учреждения | IBM Исследовательский центр Альмадена |
Миклош Айтай (родился 2 июля 1946 года) специалист по информатике в IBM Исследовательский центр Алмадена, США. В 2003 году он получил приз Кнута за его многочисленные вклады в эту область, включая классический алгоритм сети сортировки (разработанный совместно с J. Komlós и Эндре Семереди ), экспоненциальные нижние границы, суперлинейные компромиссы во времени и пространстве для ветвящихся программ и другие "уникальные и впечатляющие" результаты.
Один из Результаты Аджтаи утверждают, что длина доказательств в логике высказываний принципа ящика для n элементов растет быстрее, чем любого полинома от n. Он также доказал, что утверждение «любые две счетные структуры, которые эквивалентны второму порядку, также изоморфны » одновременно согласовано с и независимый из ZFC. Аджтай и Семереди доказали теорему об углах, важный шаг к многомерным обобщениям теоремы Семереди. С помощью Комлоса и Семереди он доказал верхнюю границу ct / log t для числа Рамсея R (3, t). Соответствующая нижняя граница была доказана Кимом только в 1995 году, что принесло ему Премию Фулкерсона. С помощью Chvátal, Newborn и Szemerédi Айтаи доказал неравенство числа пересечений, что любой рисунок графа с n вершинами и m ребра, где m>4n, имеют не менее m / 100n пересечений. Аджтай и Дворк разработали в 1997 году решеточную криптосистему с открытым ключом ; Аджтай проделал большую работу по задачам решетки. За свой большой вклад в теоретическую информатику он получил премию Кнута.
Аджтай получил степень кандидата наук в 1976 году в Венгерской академии наук. Наук. С 1995 года он был внешним членом Венгерской академии наук.
. В 1998 году он был приглашенным спикером Международного конгресса математиков в Берлине. В 2012 году он был избран членом Американской ассоциации развития науки.
.