Jump to content

Йохан Хастад

Йохан Хастад
Рожденный ( 1960-11-19 ) 19 ноября 1960 г. (63 года)
Национальность Шведский
Альма-матер
Награды
Научная карьера
Поля Информатика
Учреждения Королевский технологический институт 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 ]

  1. ^ Йохан Хостад в проекте «Математическая генеалогия»
  2. Институт Саймонса: Йохан Хостад , получено 5 апреля 2018 г.
  3. ^ Премия Гёделя 1994 г. , получено 5 апреля 2018 г.
  4. ^ Премия Гёделя 2011 г. , получено 5 апреля 2018 г.
  5. ^ Хостад, Йохан (1998). «Об аппроксимации NP-трудных задач оптимизации» . Док. Математика. (Билефельд) Extra Vol. ICM Берлин, 1998, вып. III . стр. 441–450.
  6. ^ Список членов Американского математического общества , получено 19 января 2013 г.
  7. ^ Стипендиаты ACM 2018 удостоены награды за важнейшие достижения, лежащие в основе цифровой эпохи , Ассоциация вычислительной техники , 5 декабря 2018 г.
  8. ^ Премия Кнута 2018 присуждена Йохану Хостаду (PDF) , ACM, 6 августа 2018 г.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 95308a0fd5c25bd9a4f4248d5737e3d0__1709428140
URL1:https://arc.ask3.ru/arc/aa/95/d0/95308a0fd5c25bd9a4f4248d5737e3d0.html
Заголовок, (Title) документа по адресу, URL1:
Johan Håstad - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)