Хостад, Юхан
Юхан Хостад
Награды и премии
- Золотая медаль Международной математической олимпиады (1977)
- Премия ACM за докторскую диссертацию (1985)
- Премия Гёделя (1994, 2011)
- Премия Кнута (2018)
Юхан Торкель Хостад (швед. Johan Torkel Håstad; [Нет даты!]) — шведский учёный в области теоретической информатики. Известен работами по теории сложности вычислений. Лауреат премии Гёделя (1994, 2011) и премии ACM за докторскую диссертацию (1986).
Биография[править]
В 1981 году получил степень бакалавра наук по математике в Стокгольмском университете, в 1984 году — степень магистра наук по математике в Уппсальском университете, а в 1986 году — степень доктора философии по математике в Массачусетском технологическом институте. С 1988 года работает профессором теоретической информатики в Королевском технологическом институте в Стокгольме, в 1992 году стал полным профессором. С 2001 года является членом Королевской шведской академии наук.
Диссертация Хостада и премия Гёделя 1994 года связаны с его работой над нижними оценками размера булевых схем постоянной глубины для функции чётности. После того как Эндрю Яо доказал, что такие схемы требуют экспоненциального размера, Хостад доказал почти оптимальные нижние оценки необходимого размера с помощью своей леммы о переключении. Она стала важным техническим инструментом в сложности схем с применениями в обучаемости, иерархии IP и системах доказательств.
В 2011 году он получил вторую премию Гёделя за работу над оптимальными результатами неаппроксимируемости. В частности, он улучшил PCP-теорему (которая была отмечена той же премией в 2001 году), предложив вероятностного верификатора для NP-задач, который считывает только три бита. В дальнейшем он использовал эти результаты для доказательства результатов в области трудности аппроксимации.
В 1998 году Хостад был приглашённым докладчиком на Международном конгрессе математиков в Берлине[1]. В 1999 году он читал лекции Эрдёша в Еврейском университете в Иерусалиме. В 2012 году стал действительным членом Американского математического общества[2]. В 2018 году был избран действительным членом ACM за «вклад в сложность схем, аппроксимируемость и неаппроксимируемость, а также в основы псевдослучайности»[3].
В 2018 году получил премию Кнута «за долгий и непрерывный ряд прорывных достижений в основах информатики, оказавших огромное влияние на многие области, включая оптимизацию, криптографию, параллельные вычисления и теорию сложности»[4].
Примечания[править]
- ↑ Håstad, Johan On approximating NP-hard optimization problems // Doc. Math. (Bielefeld) Extra Vol. ICM Berlin, 1998, vol. III. — 1998. — С. 441–450.
- ↑ List of Fellows of the American Mathematical Society. Проверено 8 июня 2026.
- ↑ 2018 ACM Fellows Honored for Pivotal Achievements that Underpin the Digital Age. Ассоциация вычислительной техники (2018-12-05). Проверено 8 июня 2026.
- ↑ 2018 Knuth Prize is Awarded to Johan Håstad. ACM (2018-08-06). Проверено 8 июня 2026.
Ссылки[править]
 | Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Хостад, Юхан», расположенная по адресу:
Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?». |
|---|
- Родившиеся 19 ноября
- Родившиеся в 1960 году
- Персоналии по алфавиту
- Учёные в области информатики Швеции
- Лауреаты премии Гёделя
- Лауреаты премии Кнута
- Выпускники Уппсальского университета
- Выпускники Стокгольмского университета
- Преподаватели Королевского технологического института
- Действительные члены Американского математического общества
- Действительные члены Ассоциации вычислительной техники
- Выпускники Школы наук Массачусетского технологического института
- Члены Шведской королевской академии наук