Миклош Айтай

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

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

Содержание

  • 1 Избранные результаты
  • 2 Биоданные
  • 3 Библиография
  • 4 Избранные статьи
  • 5 Ссылки
  • 6 Внешние ссылки

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

Один из Результаты Аджтаи утверждают, что длина доказательств в логике высказываний принципа ящика для n элементов растет быстрее, чем любого полинома от n. Он также доказал, что утверждение «любые две счетные структуры, которые эквивалентны второму порядку, также изоморфны » одновременно согласовано с и независимый из ZFC. Аджтай и Семереди доказали теорему об углах, важный шаг к многомерным обобщениям теоремы Семереди. С помощью Комлоса и Семереди он доказал верхнюю границу ct / log t для числа Рамсея R (3, t). Соответствующая нижняя граница была доказана Кимом только в 1995 году, что принесло ему Премию Фулкерсона. С помощью Chvátal, Newborn и Szemerédi Айтаи доказал неравенство числа пересечений, что любой рисунок графа с n вершинами и m ребра, где m>4n, имеют не менее m / 100n пересечений. Аджтай и Дворк разработали в 1997 году решеточную криптосистему с открытым ключом ; Аджтай проделал большую работу по задачам решетки. За свой большой вклад в теоретическую информатику он получил премию Кнута.

Biodata

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

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

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

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

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

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

Ссылки

Внешние ссылки

.

Последняя правка сделана 2021-05-30 11:38:52
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте