Max Home IndustryИзраильский математик и ученый-компьютерщик Ави Вигдерсон, который в дополнение к большой оригинальной работе в области вычислений и теории сложности, обучил многие поколения теоретиков-информатиков в рамках своей программы приглашенных и постдоков в Институте перспективных исследований в Принстоне, в этом году получил награду приз Дональда Э. Кнута ACM / IEEE.
Эта ежегодная премия в размере 5000 долларов, учрежденная в 1996 г., присужденная Специальной группой по интересам ACM по алгоритмам и теории вычислений, пользуется большим авторитетом, и любой член сообщества теоретиков информатики может выдвинуть кандидата. Премия названа в честь Дональда Кнута из Стэнфордского университета, которого называют «отцом анализа алгоритмов», а также называют «Евклидом информатики» и присуждается отдельным лицам за вклад в основы информатики.
На 2019 год комитет по присуждению премии Кнута под председательством Аврима Блюма выбрал Ави Вигдерсона для его работы в таких областях, как рандомизированные вычисления, криптография, сложность схем, сложность доказательства, параллельные вычисления и понимание фундаментальных свойств графа.
Цитата из цитаты:
Работа Вигдерсона произвела революцию в нашем понимании случайности в вычислениях. В серии результатов он показал при широко распространенных вычислительных предположениях, что любой вероятностный алгоритм с полиномиальным временем может быть полностью дерандомизирован. Другими словами, случайность не требуется для вычислений за полиномиальное время.
В цитировании упоминаются соавторы основополагающих работ Вигдерсона в этой области — Нисан в случае «Жесткость против случайности»; Бабай, Фортноу и Нисан за «BPP имеет субэкспоненциальное моделирование во времени, если EXPTIME не имеет опубликованных доказательств» и Impagliazzo за «P = BPP, если E требует экспоненциальных схем: дерандомизация леммы XOR». Следует также отметить, что эта последняя статья, которая показала, что P = BPP подразумевается из предположения, что существуют функции, которые могут быть вычислены машинами Тьюринга с экспоненциальным временем, которые не могут быть вычислены схемами субэкспоненциального размера в худшем случае, является одно из самых убедительных доказательств того, что P = BPP.
Его две знаковые работы по криптографии, в которых он показал, как можно безопасно вычислить любую функцию в присутствии нечестных сторон, были сотрудничество с Голдрайхом и Микали, а также с Бен-Ором и Голдвассером соответственно.
В цитировании также отмечается:
Вдобавок, возникший из криптографии, но с приложениями во многих областях теоретической информатики, Вигдерсон с Бен-Ором, Голдвассером и Килианом определили модель многопроверочных интерактивных доказательств. Эта модель впервые показала, как машина с полиномиальным временем могла бы проверить экспоненциально длинное доказательство. Эта идея оказала существенное влияние и, среди прочего, привела к знаменитой теореме PCP и потоку последующих работ по твердости приближения.
Переходя к параллельным вычислениям Основополагающие результаты Виджерсона о моделях параллельных вычислений включают, с Карпом и Упфалом, первый алгоритм RNC для построения идеального соответствия в графе и, с Карпом, первый алгоритм ЧПУ для поиска максимального независимого множества в графе как а также ряд фундаментальных результатов о нижней оценке.
Что касается теории графов:
Вместе с Рейнгольдом, Вадханом и Капалбо Вигдерсон дал первые эффективные комбинаторные конструкции расширительных графов, важного класса высокосвязных разреженных графов. До этой работы были известны только алгебраические конструкции. Разработка Виджерсоном конструкций комбинаторных расширителей позволила получить ряд важных последующих результатов, включая детерминированный алгоритм лог-пространства Рейнгольда для st-связности.
Предыдущие награды Вигдерсона — это в 1994 году премия Неванлинны за его работу по вычислительной сложности, а в 2009 году вместе с Омером Рейнгольдом и Салилом Вадханом — премия Гёделя за работу над зигзагообразным произведением графов, методом объединения меньших графов в производят более крупные, используемые при построении графов-расширителей. Он был избран членом Национальной академии наук в 2013 году и был избран членом ACM в 2018 году за вклад в теоретическую информатику и математику.
В качестве биографических подробностей, согласно Википедии, Ави Вигдерсон родился в 1956 году и в 1980 году окончил Технион в Хайфе, Израиль, а затем поступил в Принстонский университет, где его докторскую степень в области вычислительной сложности контролировал Ричард Липтон, сам победитель конкурса Кнута. Приз (2014), а также ответственный за номинацию Виджерсона. После краткосрочных должностей в Калифорнийском университете в Беркли, исследовательском центре IBM Almaden и Исследовательском институте математических наук в Беркли он поступил на факультет Еврейского университета в 1986 году. В 1999 году он также занял должность в Институте перспективных исследований. , а в 2003 году он отказался от должности в Еврейском университете и перешел на постоянное место жительства в IAS.
Если вас интересует более полный отчет о ранней жизни Ави Вигдерсона, его любви к математике и его пути в информатику, посмотрите первые несколько минут этого интервью с Алоном Розеном с PCP Fest 2018:
Отвечая на вопрос о своем детстве, Вигдерсон рассказывает, как его родители, выходцы из Польши, пережившие холокост, приехали в Хайфу в начале 1950-х годов и вырастили трех сыновей в двухкомнатной квартире в бедном районе, который в детстве он считал идиллическим. . Его отец привил ему любовь или математику, которые воспитывались в школе, где его вдохновил учитель-эмигрант из России, который выучил иврит у мальчиков, которых он обучал математике.
Интервью, которое длится более 100 минут и которое я еще не смотрел полностью, позже переходит к теме, обозначенной его названием — Теория сложности и PCP. В заключительных протоколах Вигдерсон говорит о своей любви к преподаванию и лекциям, а также отмечает ценность случайности, одной из тем, за которую он удостоен премии Кнута.