Математик Ави Вигдерсон удостоен Премии Тьюринга за революционный вклад в теорию вычислений

Математик Ави Вигдерзон (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-полные задачи. Они показали, что решение каждой такой проблемы может быть доказано с помощью доказательства с нулевым разглашением.

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

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


Источник