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