Міклош Айтай

Міклош Айтай
угор. Ajtai Miklós
Народився	2 липня 1946(1946-07-02) (77 років) Будапешт, Друга Угорська республіка
Місце проживання	Сан-Хосе
Країна	Угорщина
Діяльність	математик, інформатик, інженер
Alma mater	Будапештський університет (1976)
Галузь	теорія складності обчислень
Заклад	IBM Університет Макгілла Університет Каліфорнії в Сан-Дієго Массачусетський технологічний інститут
Науковий керівник	András Hajnald
Аспіранти, докторанти	András Kornaid
Членство	Угорська академія наук Національна академія наук США
Батько	Miklós Ajtaid
Нагороди	премія Кнута (2003) член Американської асоціації сприяння розвитку наукиd (2012)

Міклош Айтай (народився 2 липня 1946 року) — американський комп'ютерний фахівець у IBM Almaden Research Center угорського походження.

Навчання та громадська діяльність

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

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

Наукова діяльність

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

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

Нагороди

У 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
• Міклош Айтай(англ.) в проєкті «Математична генеалогія».(англ.) в проекті «Математична генеалогія».