Математик Ави Вигдерзон (Avi Wigderson) из Института перспективных исследований (IAS) в Принстоне удостоен Премии Тьюринга 2023 года. Эта престижная премия, учреждённая Ассоциацией вычислительной техники (ACM) и присуждаемая за вклад в области информатики, включает финансовое поощрение в размере $1 000 000, благодаря поддержке Google. Она названа в честь математика Алана Тьюринга, чьи исследования лежат в основе современной теории вычислений.

Премия была присуждена Вигдерзону за его фундаментальный вклад в теорию вычислений и ведущую роль в развитии теоретической информатики. В частности, его работы по изучению роли случайности в вычислениях привели к изменению общего понимания этого вопроса. Вигдерзон также является обладателем Абелевской премии 2021 года, что делает его первым человеком, удостоенным обеих престижных наград.

Источник: Andrea Kane / Institute for Advanced Study

Он получил признание за свои исследования в области дерандомизации и псевдослучайности, которые привнесли глубокое понимание важности случайности в вычислениях. Вместе с Ноамом Нисаном (Noam Nisan) он опубликовал влиятельную статью в 1994 году, демонстрирующую, что случайность не является необходимой для эффективного решения задач. Это исследование исключило возможность преимущества вероятностных алгоритмов и обозначило роль детерминизма в вычислительной науке.

Ави Вигдерзон родился в Израиле и получил докторскую степень в области компьютерных наук в Принстоне в 1983 году. Он внёс значительный вклад в различные области информатики, включая параллельные алгоритмы, криптографию и теорию сложности.

В своих исследованиях Вигдерзон также обращает внимание на то, что вычисления происходят не только в компьютерах, но и повсюду в окружающем нас мире. Он подчёркивает, что законы природы, действующие во всех естественных процессах, также могут быть выражены с помощью математических формул и алгоритмов. Таким образом, его исследования имеют широкие приложения в различных научных областях, включая статистическую и квантовую физику, вычислительную биологию, экономику и социальные науки.

В комментарии о своей научной работе Вигдерзон отмечает, что его исследования имеют теоретический характер: «Меня не мотивируют заявки. Но я знаю, что эта фундаментальная работа находит применение. Подумайте об Алане Тьюринге. Он опубликовал математическую статью по логике в малоизвестном журнале. Она не была мотивирована применением. Но именно с этого начинается информатика. Он сам признал, что Модель, которую он предлагал, настолько проста, что её легко создать».

В середине 1980-х годов Вигдерзон, вместе с Сильвио Микали (Silvio Micali) и Одедом Гольдрейхом (Oded Goldreich), расширил идею интерактивных доказательств с нулевым разглашением на NP-полные задачи. Они показали, что решение каждой такой проблемы может быть доказано с помощью доказательства с нулевым разглашением.

«Мы обнаружили, что всё, что можно доказать, можно доказать, не раскрывая новой информации», — пояснил Вигдерзон. «Мотивация для этого исследования пришла из криптографии, где я хотел доказать, что выбрал секретный ключ правильно, но не раскрывать его. В результате мы получили очень общий подход, который теперь применяется в блокчейнах и других криптосистемах. Иногда меня удивляет трудолюбие людей, которые заинтересованы в практической реализации и хотят увидеть, как всё работает».

Ави Вигдерзон остаётся активным учёным. Его радует возможность сотрудничать каждый год с новыми группами молодых учёных. Одним из его текущих проектов является обобщение теории выпуклой оптимизации на неевклидовы условия. Эта область имеет широкое применение в машинном обучении, обработке сигналов, компьютерном зрении и системах автоматического управления. Проект Вигдерзона направлен на «обобщение теории на многообразия, которые встречаются в различных областях математики и физики, таких как квантовая теория информации и теория инвариантов, а также в информатике. Эта теория также применяется в анализе для доказательства неравенств и в алгебре для доказательства тождеств. Она широко применима, и это вдохновляет меня», — отметил он.