Міклош Айтай

Міклош Айтай здобув ступінь кандидата наук у 1976 році в Угорській Академії наук.[3] З 1995 року він є членом Угорської Академії наук.

У 1998 році він був запрошеним спікером Міжнародного конгресу математиків у Берліні[4]. У 2012 році він був обраний членом Американської асоціації розвитку науки[5].

Один з результатів наукових пошуків Міклоша Айтая свідчить, що довжина доказів у численнях висловлень з принципу Діріхле для n елементів зростає швидше, ніж будь-який многочлен у n. Він також довів, що твердження «будь-які дві зліченні множини, які є еквівалентом другого порядку, також є ізоморфічними», і вони як узгоджуються, так і не залежать від теорії множин Цермело — Френкеля (zfc).

Міклош Айтай та Ендре Семереді довели теорему про кути, що є важливим кроком для узагальнення теореми Семереді. З Комлошем та Семереді він довів верхню межу ct2 / log t для числа теореми Рамсея R (3, t). Відповідна нижня межа була доведена Кімом лише в 1995 році. За цей результат він був нагороджений премією Фалькенсона. Із Чваталом та Семереді Міклош Айтай довів нерівність числа перетину, що будь-який малюнок графіка з n вершинами та m ребрами, де m> 4n, має щонайменше м3 / 100n2 чисел схрещувань. Айтай та Дворк розробляли в 1997 році криптосистему з відкритим ключем на основі асиметричних алгоритмів шифрування. Міклош Айтай провів велику роботу з вивчення асиметричних алгоритмів шифрування. За численні внески в теоретичну комп'ютерну науку він отримав премію Кнута[6].

У 2003 році він був нагороджений премією Кнута за великий внесок в теоретичну комп'ютерну науку, включаючи класичний алгоритм сортувальної мережі (розроблений спільно з Дж. Комлосом та Ендре Семереді), експоненціальні нижні межі, суперлінійні компроміси у часовому просторі для програм розгалуження, а також інші «унікальні та вражаючі» результати.

1. Ajtai, M. (1979). Isomorphism and higher order equivalence. Annals of Mathematical Logic 16 (3): 181–203. doi:10.1016/0003-4843(79)90001-9.
2. Ajtai, M.; Komlós, J.; Szemerédi, E. (1982). Largest random component of a k-cube. Combinatorica 2 (1): 1–7. doi:10.1007/BF02579276.

• Домашня сторінка Міклоша Айтая
• Список публікацій на Microsoft Academic Search
• Міклош Айтай(англ.) в проєкті «Математична генеалогія».(англ.) в проекті «Математична генеалогія».