Йохан Хастад - Johan Håstad

Йохан Хастад
Родившийся (1960-11-19) 19 ноября 1960 г. (возраст 60)
НациональностьШвеция
Альма-матер
Награды
Научная карьера
ПоляИнформатика
УчрежденияКоролевский технологический институт
ДокторантШафрира Гольдвассер[1]

Йохан Торкель Хостад (Шведское произношение:[ˈJûːan ˈhǒːsta]; родился 19 ноября 1960 г.) Шведский теоретик-информатик наиболее известен своей работой над теория сложности вычислений. Он был получателем Премия Гёделя в 1994 и 2011 годах и ACM Премия за докторскую диссертацию в 1986 году среди других премий. Он был профессор в теоретическая информатика на Королевский технологический институт в Стокгольм, Швеция с 1988 г., став профессором в 1992 г. Он является членом Шведская королевская академия наук с 2001 года.

Он получил свой Б.С. в Математика в Стокгольмский университет в 1981 году его РС. по математике в Уппсальский университет в 1984 г. и его Кандидат наук. по математике от Массачусетский технологический институт в 1986 г.[2]

Хостад и 1994 г. Премия Гёделя касался его работы над нижняя граница по размеру постоянной глубины Булевы схемы для функция четности. После Эндрю Яо доказал, что такие схемы требуют экспоненциального размера, Хостад доказал почти оптимальные нижние оценки необходимого размера в своей работе. лемма о переключении, который стал важным техническим инструментом в сложность схемы с приложениями к обучаемость, то IP иерархия и системы доказательства.[3]

Он также получил премию Гёделя 2011 года за свою работу над оптимальными результатами несовместимости. В частности, он улучшил Теорема PCP (который получил тот же приз в 2001 г.), чтобы дать вероятностный верификатор для НП проблемы, которые читают только три бита. Далее он использовал эти результаты для доказательства результатов в твердость приближения.[4]

В 1998 году Хостад был приглашенным спикером Международный конгресс математиков в Берлине.[5] В 1999 году он был Лектор Эрдёша на Еврейский университет Иерусалима. В 2012 году он стал сотрудником Американское математическое общество.[6] Он был избран Член ACM в 2018 году за «вклад в сложность схем, аппроксимируемость и непроксимируемость, а также основы псевдослучайности».[7]

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

  1. ^ Йохан Хастад на Проект "Математическая генеалогия"
  2. ^ Институт Саймонса: Йохан Хастад, получено 5 апреля 2018.
  3. ^ Премия Гёделя 1994, дата обращения 05.04.2018
  4. ^ Премия Гёделя 2011, дата обращения 05.04.2018
  5. ^ Хостад, Йохан (1998). «Об аппроксимации NP-сложных задач оптимизации». Док. Математика. (Билефельд) Extra Vol. ICM Berlin, 1998, т. III. С. 441–450.
  6. ^ Список членов Американского математического общества, получено 19 января 2013.
  7. ^ Стипендиаты ACM 2018 награждены за ключевые достижения, лежащие в основе цифровой эпохи, Ассоциация вычислительной техники, 5 декабря 2018

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