Миклош Айтай
Миклош Айтай | |
|---|---|
| Рожденный | 2 июля 1946 г. |
| Национальность | Венгерско-американский |
| Альма-матер | Венгерская академия наук |
| Награды | Премия Кнута (2003) [ 1 ] |
| Научная карьера | |
| Поля | Теория сложности вычислений |
| Учреждения | IBM в Альмадене Исследовательский центр |
Миклош Айтай (родился 2 июля 1946 года) — учёный-компьютерщик в IBM Исследовательском центре в Альмадене , США. В 2003 году он получил премию Кнута за многочисленные вклады в эту область, включая классический алгоритм сортирующей сети (разработанный совместно с Дж. Комлосом и Эндре Семереди ), экспоненциальные нижние границы, суперлинейные компромиссы времени и пространства для ветвящихся программ и другие». уникальные и впечатляющие» результаты. Он является членом Национальной академии наук США . [ 2 ]
Избранные результаты
[ редактировать ]Один из результатов Айтая утверждает, что длина доказательств в логике высказываний принципа «ячейки» для n элементов растет быстрее, чем любой полином от n . Он также доказал, что утверждение «любые две счетные структуры , эквивалентные второго порядка, также изоморфны » одновременно совместимо с и не зависит от него ZFC . Айтай и Семереди доказали теорему об углах , что стало важным шагом на пути к многомерному обобщению теоремы Семереди . С Комлошем и Семереди он доказал свою силу. 2 /log t верхняя граница числа Рамсея R (3, t ). Соответствующая нижняя оценка была доказана Кимом только в 1995 году, за что он получил премию Фулкерсона . Вместе с Хваталом , Ньюборном и Семереди Айтай доказал неравенство числа пересечений , согласно которому любой рисунок графа с n вершинами и m ребрами, где m > 4 n , имеет по крайней мере m 3 / 100 н. 2 переправы . В 1997 году Айтай и Дворк разработали решетчатую криптосистему с открытым ключом ; Аджтай провёл обширную работу по проблемам решеток . За свой многочисленные вклады в теоретическую информатику он получил премию Кнута. [ 1 ]
Биография
[ редактировать ]Айтай получил степень кандидата наук в 1976 году в Венгерской академии наук . [ 3 ] С 1995 года — внешний член Венгерской академии наук .
В 1998 году он был приглашенным докладчиком на Международном конгрессе математиков в Берлине. [ 4 ] В 2012 году он был избран членом Американской ассоциации содействия развитию науки . [ 5 ] В 2021 году он был избран членом Национальной академии наук. [ 6 ]
Библиография
[ редактировать ]- Айтай, Миклош (10 мая 2008 г.). «Оптимальные нижние оценки параметров Коркина-Золотарева решетки и алгоритма Шнорра для задачи кратчайшего вектора» . Теория вычислений . 4 : 21–51. дои : 10.4086/toc.2008.v004a002 .
- Айтай, Миклош (5 октября 2005 г.). «Нелинейная нижняя граница времени для программ с логическим ветвлением» . Теория вычислений . 1 : 149–176. дои : 10.4086/toc.2005.v001a008 .
- Айтай, М. (1996). «Генерация сложных примеров решетчатых задач (Расширенное резюме)». Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '96 . стр. 99–108. дои : 10.1145/237814.237838 . ISBN 978-0-89791-785-8 . S2CID 6864824 .
Избранные статьи
[ редактировать ]- Аджтай, М. (сентябрь 1979 г.). «Изоморфизм и эквивалентность высшего порядка». Анналы математической логики . 16 (3): 181–203. дои : 10.1016/0003-4843(79)90001-9 .
- Аджтай, М.; Комлос, Дж.; Семереди, Э. (март 1982 г.). «Самая большая случайная компонента k -куба». Комбинаторика . 2 (1): 1–7. дои : 10.1007/BF02579276 . S2CID 7903662 .
Ссылки
[ редактировать ]- ^ Jump up to: а б «Архивная копия» . Архивировано из оригинала 14 мая 2021 г. Проверено 10 февраля 2015 г.
{{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка ) - ^ «Вести Национальной академии наук» . 26 апреля 2021 г. Проверено 1 июля 2021 г.
Вновь избранные члены и их принадлежность на момент выборов: ... Айтаи, Миклош; Почетный исследователь IBM, Исследовательский центр IBM в Альмадене, Лос-Гатос, Калифорния.
- ^ Венгерская академия наук, Альманах, 1986, Будапешт.
- ^ Айтай, Миклош (1998). «Сложность наихудшего случая, сложность среднего случая и задачи решетки» . Документа Математика : 421–428.
- ↑ Члены AAAS избраны научными сотрудниками , AAAS, 29 ноября 2012 г.
- ^ «Национальная академия наук избирает новых членов, включая рекордное количество женщин, и международных членов» . nasonline.org . 26 апреля 2021 г. Проверено 28 апреля 2021 г.
Внешние ссылки
[ редактировать ]- Домашняя страница Миклоша Айтая
- Публикации Миклоша Айтая , индексируемые Microsoft Academic
- Миклош Айтай в проекте «Математическая генеалогия»
   | Эта статья о венгерском ученом незавершена . Вы можете помочь Википедии, расширив ее . |
- 1946 года рождения
- Живые люди
- Лауреаты премии Кнута
- Венгерские математики XX века
- Венгерские математики XXI века
- Венгерские ученые-компьютерщики
- Члены Венгерской академии наук
- Члены Американской ассоциации содействия развитию науки
- Теоретики-компьютерщики
- Венгерские эмигранты в США
- Американские ученые-компьютерщики
- сотрудники IBM
- Члены Национальной академии наук США
- Венгерский учёный незавершенный
- Незавершённые статьи по компьютерным наукам