Миклош Айтай - Miklós Ajtai

Родная форма этого личное имя является Айтай Миклош. В этой статье используется Западный порядок имен при упоминании лиц.
Миклош Айтай
Родившийся (1946-07-02) 2 июля 1946 г. (возраст 74)
Будапешт, Вторая Венгерская Республика
НациональностьВенгерско-американский
Альма-матерВенгерская Академия Наук
НаградыПриз Кнута (2003)[1]
Научная карьера
ПоляТеория вычислительной сложности
УчрежденияIBM Исследовательский центр Альмадена

Миклош Айтай (родился 2 июля 1946 г.) специалист в области информатики на IBM Исследовательский центр Альмадена, Соединенные Штаты. В 2003 году он получил Приз Кнута за его многочисленные вклады в эту область, в том числе классический сортировочная сеть алгоритм (разработан совместно с Я. Комлос и Эндре Семереди ), экспоненциальные нижние границы, суперлинейные пространственно-временные компромиссы для ветвящихся программ и другие «уникальные и впечатляющие» результаты.

Избранные результаты

Один из результатов Аджтай утверждает, что длина доказательств в логика высказываний из принцип голубятни за п предметы растут быстрее любых многочлен в п. Он также доказал, что утверждение «любые два счетный структуры которые эквивалентны второго порядка, также изоморфный "это оба последовательный с и независимый из ZFC. Аджтай и Семереди доказал теорема углов, важный шаг к многомерным обобщениям Теорема Семереди. С Komlós и Семереди он доказал ct2/бревно т верхняя граница для Число Рамсея р(3,т). Соответствующая оценка снизу доказана Ким только в 1995 году, что принесло ему Премия Фулкерсона. С Chvátal, Новорожденный, и Семереди, Аджтай доказал пересечение числового неравенства, что любой рисунок графа с п вершины и м края, где м > 4п, имеет по крайней мере м3 / 100п2 переходы. Аджтай и Dwork разработал в 1997 году решетчатую криптосистема с открытым ключом; Аджтай проделал большую работу над проблемы решетки. За его многочисленные вклады в теоретическую информатику он получил премию Кнута.[1]

Биоданные

Аджтай получил Кандидат наук степень в 1976 г. Венгерская Академия Наук.[2] С 1995 года он был внешним членом Венгерская Академия Наук.

В 1998 году он был приглашенным спикером Международный конгресс математиков в Берлине.[3] В 2012 году он был избран Член Американской ассоциации развития науки.[4]

Библиография

  • Айтаи, Миклош: Оптимальные нижние границы параметров Коркина-Золотарева решетки и для алгоритма Шнорра для кратчайшей векторной задачи, в: Theory of Computering, Vol. 4. С. 21-51.[5]
  • Айтай, Миклош: Нижняя граница нелинейного времени для булевых ветвящихся программ, в: Теория компьютеризации, т. 1. С. 149-176.[5]
  • Айтай, Миклош: Создание трудных экземпляров решеточных задач. Электронный коллоквиум по завершенности вычислений, стр. 1-29.[6]

Избранные статьи

  1. Айтай, М. (1979), "Изоморфизм и эквивалентность более высокого порядка", Анналы математической логики, 16 (3): 181–203, Дои:10.1016/0003-4843(79)90001-9.
  2. Ajtai, M .; Комлос, Я.; Семереди, Э. (1982), «Наибольшая случайная составляющая k-куб », Комбинаторика, 2 (1): 1–7, Дои:10.1007 / BF02579276.

Рекомендации

  1. ^ а б http://www.sigact.org/Prizes/Knuth/2003.html
  2. ^ Magyar Tudományos Akadémia, Альманах, 1986, Будапешт.
  3. ^ Айтай, Миклош (1998). «Сложность наихудшего случая, сложность среднего случая и решеточные задачи». Док. Математика. (Билефельд) Extra Vol. ICM Berlin, 1998, т. III. С. 421–428.
  4. ^ Члены AAAS избраны в качестве стипендиатов, AAAS, 29 ноября 2012 г.
  5. ^ а б "Статьи Миклоша Айтая". Теория вычислений. Получено 23 октября 2019.
  6. ^ «Создание жестких примеров решеточных задач» (PDF). semanticscholar.org. Получено 23 октября 2019.

внешняя ссылка