Премия Гёделя традиционно считается одной из наиболее престижных наград в области теоретической информатики и вычислительной математики. Каждый год она присуждается авторам выдающихся результатов, которые оказывают глубокое влияние на развитие теории вычислений. В 2025 году лауреатами стали учёные Эшан Чаттопадхаи и Дэвид Цукерман за их прорывную работу по созданию явного двухисточникового экстрактора и устойчивых функций. Их статья, опубликованная в 2019 году в Annals of Mathematics, полностью изменила представления о том, как можно получить качественный источник случайности из двух независимых, но несовершенных источников. Эта проблема оставалась нерешённой почти три десятилетия, представляя собой фундаментальную задачу в теории вычислений и криптографии.
Модель случайных процессов и их экстракция играют ключевую роль во многих областях компьютерных наук, включая криптографию, алгоритмы и распределённые вычисления. Основная задача состоит в том, чтобы получить максимально равномерное распределение случайных битов из источников, которые сами по себе не являются полностью случайными и могут иметь ограниченную энтропию. В течение долгого времени существовали методы экстракции случайности, использующие один источник с дополнительным вспомогательным зерном случайности (seeded extractors). Однако задача создания двухисточникового экстрактора — системы, которая может объединять два независимых, но недостаточно случайных источника в один практически идеальный — оставалась открытой и крайне сложной. Работа Чаттопадхаи и Цукермана стала настоящим прорывом, показав явную конструкцию таких двухисточниковых экстракторов с очень низким порогом мин-энтропии, приближающимся к полилогарифмическому уровню.
Это означает, что даже если исходные источники имеют довольно ограниченную случайность, их можно эффективно преобразовать в почти равномерно распределённые случайные биты. Такая возможность расширяет горизонты применения теории случайности в практических и теоретических задачах. Ключевым элементом их подхода стали устойчивые функции, или resilient functions. Изначально эти функции были разработаны в контексте распределённых вычислений, где они служили для обеспечения надёжности систем в случае сбоев или влияния малой части некорректных данных. Идея использовать устойчивые функции в контексте экстракции случайности была неожиданной, но именно благодаря этому удалось преодолеть долгосрочные препятствия в построении двухисточниковых экстракторов.
Чаттопадхаи и Цукерман разработали новую явную устойчивую функцию, обладающую уникальными характеристиками: она является монотонной, может быть вычислена с помощью AC0-схем (силы вычислительных моделей с ограниченной глубиной и верхним ограничением на логические операции) и демонстрирует улучшенные параметры устойчивости по сравнению с предыдущими разработками. Это сочетание свойств позволило им интегрировать эту функцию в композицию с двумя другими инструментами — не модифицируемым (non-malleable) экстрактором с семенем и обособленным семплером. Такая композиция образовала мощный двухисточниковый экстрактор с доказательствами качества работы, базирующимися на теории псевдослучайности. Фундаментальное значение в анализе конструкции имела работа Бравермана, доказавшего, что полилогарифмическая независимость достаточно хороша для имитации случайных чисел в схемах AC0. Это открыло неожиданные связи между различными направлениями исследований в области псевдослучайности, которые ранее считались разрозненными.
Таким образом, работа лауреатов 2025 года не только решала конкретную техническую задачу, но и сплотила разрозненные концепции в единую теоретическую картину. Применение результатов Чаттопадхаи и Цукермана выходит далеко за рамки чистой теории. Надёжное извлечение случайности крайне важно для криптографических протоколов, построения случайных алгоритмов, а также для обеспечения устойчивости распределённых вычислительных систем. Появление эффективных двухисточниковых экстракторов с низкими требованиями к энтропии позволяет существенно повысить безопасность и надёжность современных вычислительных технологий. Комитет по присуждению премии Гёделя в 2025 году включал ведущих исследователей из разных стран — профессоров Миколая Боянчика из Варшавского университета, Артура Чузмая из Университета Уорика, Ювала Ишая из Техниона, Анну Карлин из Университета Вашингтона, Марту Квятковскую из Оксфордского университета и во главе с Тимом Раудгарденом из Колумбийского университета.
