Max Home IndustryШведский ученый-теоретик информатики Йохан Хостад был назван лауреатом премии Дональда Э. Кнута 2018 года за вклад в теорию вычислительной сложности.
Названная в честь Дональда Кнута из Стэнфордского университета, которого называли «отцом анализа алгоритмов», а также прозвали «Евклидом компьютерных наук», эта ежегодная премия была учреждена в 1996 году и включает в себя премию в размере 5000 долларов. Она присуждается отдельным лицам за вклад в основы информатики и совместно присуждается Группой специальных интересов ACM по алгоритмам и теории вычислений (SIGACT) и Техническим комитетом IEEE Computer Society по математическим основам вычислительной техники (TCMF) и представлена поочередно в ACM Симпозиум по теории вычислительной техники и на Симпозиуме IEEE по основам информатики (FOCS), которые являются одними из самых престижных конференций в области теоретической информатики.
В этом году лауреатом стал Йохан Торкель Хостад, профессор компьютерных наук Королевского технологического института KTH в Стокгольме.:
его долгая и устойчивая история знаковых прорывов в основах компьютерных наук, оказавших значительное влияние на многие области, включая оптимизацию, криптографию, параллельные вычисления и теорию сложности.
В объявлении ACM говорится:
Многочисленные плодотворные работы Хостада не только разрешили давние проблемы, связанные с нижними границами схемы, генерацией псевдослучайных чисел и аппроксимируемостью, но и внедрили трансформационные методы, которые фундаментально повлияли на большую часть последующих работ в этих областях.
Более подробная информация содержится в цитате СИГАКТА, в которой упоминаются три конкретных прорыва, два из которых ранее были признаны премией Геделя, которую он выиграл в 1994 и 2011 годах.
С помощью своей элегантной леммы переключения он получил почти оптимальную экспоненциальную нижнюю границу размера булевых схем постоянной глубины для функции четности, которая … имело огромное значение для теории структурной сложности.
Работа Хостада в области вероятностно проверяемых доказательств (PCP) и аппроксимируемости задач оптимизации изменила эту область. … Хостад построил почти оптимальные PCPS, где оптимальность сохраняется в отношении таких параметров, как амортизированная сложность свободного бита и общее количество запросов.
Совместная статья Хостада с Расселом Импальяццо, Леонидом Левиным и Майклом 1 Луби “Генератор псевдослучайных чисел из любой односторонней функции” является жемчужиной в теории сложности и криптографии …. [и] обеспечил конечный результат, доказав, что псевдослучайные генераторы существуют тогда и только тогда, когда существуют односторонние функции. Таким образом, два фундаментальных явления в их наиболее общей и “чистой” форме — т. Е. вычислительная сложность и генерация псевдослучайности — оказываются эквивалентными.
Профессор Хостаду будет вручен сертификат на 59-м ежегодном симпозиуме по основам компьютерных наук (FOCS 2018) в Париже, Франция, 7-9 октября.