Миклош Айтай (родился 2 июля 1946 года) — учёный-компьютерщик в исследовательском центре IBM Almaden , США. В 2003 году он получил премию Кнута за многочисленные вклады в эту область, включая классический алгоритм сортировочной сети (разработанный совместно с Дж. Комлошем и Эндре Семереди ), экспоненциальные нижние границы, сверхлинейные компромиссы времени и пространства для ветвящихся программ и другие «уникальные и впечатляющие» результаты. Он является членом Национальной академии наук США . [2]
Один из результатов Аджтая гласит, что длина доказательств в пропозициональной логике принципа ящика для n элементов растет быстрее, чем любой полином от n . Он также доказал, что утверждение «любые две счетные структуры , которые эквивалентны во втором порядке, также изоморфны » одновременно согласуется с ZFC и не зависит от него . Аджтай и Семереди доказали теорему об углах , важный шаг к обобщениям теоремы Семереди на более высокие размерности . Совместно с Комлошем и Семереди он доказал верхнюю границу ct 2 /log t для числа Рамсея R (3, t ). Соответствующая нижняя граница была доказана Кимом только в 1995 году, результат, который принес ему премию Фулкерсона . Совместно с Хваталом , Ньюборном и Семереди , Айтай доказал неравенство числа пересечений , что любой рисунок графа с n вершинами и m ребрами, где m > 4 n , имеет по крайней мере m 3 / 100 n 2 пересечений . Айтай и Дворк разработали в 1997 году криптосистему с открытым ключом на основе решетки ; Айтай проделал обширную работу по проблемам решеток . За его многочисленные вклады в теоретическую информатику он получил премию Кнута. [1]
Айтай получил степень кандидата наук в 1976 году в Венгерской академии наук . [3] С 1995 года он является внешним членом Венгерской академии наук .
В 1998 году он был приглашенным докладчиком Международного конгресса математиков в Берлине. [4] В 2012 году он был избран членом Американской ассоциации содействия развитию науки . [5] В 2021 году он был избран членом Национальной академии наук. [6]
{{cite web}}: CS1 maint: архивная копия как заголовок ( ссылка )избранные члены и их принадлежность к организациям на момент выборов: ... Айтай, Миклош; почетный исследователь IBM, исследовательский центр IBM Almaden, Лос-Гатос, Калифорния.