Йохан Торкель Хастад ( шведское произношение: [ˈjûːan ˈhǒːsta] ; родился 19 ноября 1960 г.) - шведский теоретик-компьютерщик, наиболее известный своими работами по теории сложности вычислений . Он был лауреатом премии Гёделя в 1994 и 2011 годах и премии ACM за докторскую диссертацию в 1986 году, а также других призов. Он был профессором в теоретической информатики в Королевском технологическом институте в Стокгольме , Швеция с 1988 года, став полным профессором в 1992 году является членом Шведской королевской академии наук с 2001 года.
Йохан Хастад | |
---|---|
Родившийся | 19 ноября 1960 г. |
Национальность | Швеция |
Альма-матер | |
Награды |
|
Научная карьера | |
Поля | Информатика |
Учреждения | Королевский технологический институт |
Докторант | Шафрира Гольдвассер [1] |
Он получил степень бакалавра в математике в Стокгольмском университете в 1981 году, его MS в области математики в университете Упсалы в 1984 году и его Ph.D. по математике в Массачусетском технологическом институте в 1986 г. [2]
Диссертация Хостада и премия Гёделя 1994 года касались его работы по оценке снизу размера булевых схем постоянной глубины для функции четности . После того, как Эндрю Яо доказал, что такие схемы требуют экспоненциального размера, Хастад доказал почти оптимальные нижние границы необходимого размера с помощью своей леммы о переключении , которая стала важным техническим инструментом в области сложности схем с приложениями для обучаемости , иерархии IP и систем доказательства . [3]
Он также получил премию Гёделя 2011 года за свою работу над оптимальными результатами несовместимости. В частности, он улучшил теорему PCP (которая выиграла тот же приз в 2001 г.), чтобы дать вероятностный верификатор для задач NP, который считывает только три бита. Далее он использовал эти результаты для доказательства точности приближения . [4]
В 1998 году Хостад был приглашенным спикером Международного конгресса математиков в Берлине. [5] В 1999 году он был лектором Эрдёша в Еврейском университете Иерусалима . В 2012 году он стал членом Американского математического общества . [6] Он был избран членом ACM в 2018 году за «вклад в сложность схем, аппроксимируемость и непроксимируемость, а также основы псевдослучайности». [7]
Рекомендации
- ^ Джоен Хастад на Математическая генеалогия
- ^ Simons институт: Джоен Хастад , извлекаться 2018-04-05.
- ^ 1994 Гедель премии , извлекаться 2018-04-05
- ^ 2011 Гедель премии , извлекаться 2018-04-05
- ^ Håstad, Йохан (1998). «Об аппроксимации NP-сложных задач оптимизации» . Док. Математика. (Билефельд) Extra Vol. ICM Berlin, 1998, т. III . С. 441–450.
- ^ Список членов Американского математического общества , получено 19 января 2013 г.
- ^ Стипендиаты ACM 2018 отмечены за ключевые достижения, лежащие в основе цифровой эпохи , Ассоциация вычислительной техники , 5 декабря 2018 г.
Внешние ссылки
- Домашняя страница Йохана Хостада
- Результаты Йохана Хостада на Международной математической олимпиаде