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