Пасин Манурангси: доказательство того, на что не способны компьютеры

В июле 2011 года в тайском курортном городе Паттайя прошла 23-я Международная олимпиада по информатике (IOI) — впервые в истории Таиланда, — а премьер-министр Апхисит Ветчачива (Abhisit Vejjajiva) открыл игры в числе своих последних официальных актов. Среди участников сборной был ученик Бангкокского христианского колледжа (Bangkok Christian College), который занял 14-е место из 303 участников с 524 баллами и завоевал вторую подряд золотую медаль. Он рассказал журналистам, что доволен 14-м местом, что 524 балла — это больше, чем он ожидал, и выразил надежду, что проведение олимпиады вызовет больший интерес к компьютерам среди тайской молодежи. Пятнадцать лет спустя Пасин Манурангси (Pasin Manurangsi) — один из тех исследователей, чья работа заключается в том, чтобы сообщать остальному сообществу специалистов по компьютерным наукам, какие задачи являются безнадежными.

Олимпиадный путь

Соревновательная история Манурангси читается как контролируемый эксперимент по самосовершенствованию. На IOI 2009 в Болгарии он набрал 516 баллов и занял 67-е место из 301, взяв серебро. В 2010 году в Канаде он набрал 704 балла и занял 12-е место из 297, взяв золото. В 2011 году на родной земле он снова взял золото, а Таиланд выиграл командное золото на соревновании, которое принимал впервые. Три выступления, две золотые и одна серебряная медали, и рывок на пятьдесят пять мест в мировом рейтинге между первой и второй попытками: такова траектория человека, который относился к проигрышу как к спецификации, а не как к приговору.

MIT и проблема достаточной близости

Манурангси получил степени бакалавра и магистра в Массачусетском технологическом институте (MIT), где его магистерская работа под руководством Даны Мошковиц (Dana Moshkovitz) была посвящена аппроксимационным алгоритмам для игр с проекцией (projection games). Этот выбор темы определил направление всего последующего пути. Аппроксимация — это прагматичный компромисс в данной дисциплине: когда задача не может быть решена точно за разумное время, вы довольствуетесь ответом, который гарантированно находится в пределах определенного коэффициента от оптимального. Интересный вопрос, к которому Манурангси постоянно возвращался, заключается в том, насколько хороша может быть эта гарантия, прежде чем она столкнется с математической стеной.

Беркли: страна между P и NP

Он завершил свою докторскую диссертацию в Калифорнийском университете в Беркли (University of California, Berkeley) в мае 2019 года под совместным руководством Луки Тревизана (Luca Trevisan) и Прасада Рагхавендры (Prasad Raghavendra), с Нихилом Шриваставой (Nikhil Srivastava) в составе комитета. Диссертация называлась «Аппроксимация и трудность: за пределами P и NP» (Approximation and Hardness: Beyond P and NP), и ее амбиции видны в самом названии. Классическая теория сложности классифицирует задачи на разрешимые (P) и печально известные своей сложностью (NP-полные). Диссертация Манурангси намеренно отправилась на поиски в области, которые эти категории не охватывают: задачи, которые не относятся ни к P, ни к NP-трудным, например, k-доминирующее множество (k-dominating set), k-клика (k-clique), k-биклика (k-biclique), направленные сети Штейнера (directed Steiner network) и решетчатые задачи, а также — что наиболее контринтуитивно — задачи, которые комфортно располагаются внутри P, такие как поиск ближайшей пары (closest pair) и максимального внутреннего произведения (maximum inner product), но все равно сопротивляются быстрой аппроксимации. Аннотация утверждает, что эта работа решает два давно открытых вопроса в параметризованной сложности (parameterized complexity) и предоставляет лучшие известные коэффициенты невозможности аппроксимации для ряда задач. Это диссертация о проведении границ, а не об их пересечении.

Стена самого плотного k-подграфа

Единственный результат, который сделал его знаменитым, касается задачи «самого плотного k-подграфа» (Densest k-Subgraph): имея сеть, найти k узлов, наиболее плотно соединенных между собой. Манурангси доказал, что при гипотезе экспоненциального времени никакой полиномиально-временной алгоритм не может достичь коэффициента аппроксимации лучше, чем n в степени 1/(log log n), умноженной на константу, — а при более сильном предположении Gap-ETH барьер сужается до n^f(n) для любой функции f, стремящейся к нулю, что почти эквивалентно полиномиальной сложности. Важно отметить, что конструкция обладает тем, что в области называют «идеальной полнотой» (perfect completeness): она отличает графы, которые действительно содержат k-клику, от графов, где каждый k-подграф разрежен. Статья получила награду Дэнни Левина за лучшую студенческую работу (Danny Lewin Best Student Paper Award) на STOC 2017, флагманской теоретической конференции дисциплины.

Google, конфиденциальность и справедливое деление

С июля 2019 года Манурангси работает научным сотрудником в Google Research, где его указанные области включают алгоритмы и теорию, машинный интеллект и борьбу со злоупотреблениями, и где он накопил более сотни публикаций. Центр тяжести сместился от чистой невозможности аппроксимации к дифференциальной приватности (differential privacy), теории обучения и вычислительному социальному выбору — справедливому делению, разделению консенсуса, агрегации частных рангов и генерации синтетических данных. Один из недавних результатов показывает, что разделение консенсуса с точностью до O(√(n log n)) товаров всегда существует для n агентов с монотонными полезностями, улучшая предыдущую границу. Награды продолжают поступать: лучшая статья на WAOA 2021, лучшая студенческая работа на ALT 2021, лучшая статья и почетное упоминание за лучшую статью на FORC 2026, а также признание комитета выдающейся программы на IJCAI в 2021 и 2023 годах и статус главного рецензента на NeurIPS 2023.

Обратный путь

С 2022 года он входит в состав тренерских команд для тайской олимпиады по информатике и лагерей по математической олимпиаде, а также был приглашенным членом делегации Таиланда на IOI 2024. С 2023 года он также является адъюнкт-профессором в университете CMKL, где преподает алгоритмы, структуры данных и алгоритмы сохранения конфиденциальности. Конвейер, который создал его, теперь он помогает поддерживать.

Почему Пасина называют гением

Когнитивное качество, о котором здесь идет речь, необычно специфично, и это не просто скорость. Успех на олимпиаде вознаграждает быстрое и точное решение задач в условиях ограниченного времени; сложность аппроксимации вознаграждает как раз обратное — терпение, необходимое для построения сложной редукции, доказывающей, что целый класс алгоритмов обречен. Манурангси редкость, поскольку он достиг высоких результатов в обоих направлениях, и диссертация в Беркли тому доказательство: она застолбила территорию, которой большинство исследователей избегают именно потому, что отрицательные результаты сложнее опубликовать и сложнее выполнить верно. Единственная логическая ошибка в редукции аннулирует всё.

Честный контр-аргумент существенен. Нигде в доступных источниках — его собственная домашняя страница, профиль в Google Research, диссертация или современные тайские публикации — о нем не говорится слово «гений». Его награды — это профессиональное признание комитетов конференций, которые отмечают лучшую работу в аудитории, а не разум на все времена. Теоретическая информатика также является неизменно совместной; его сотня с лишним статей — это продукт соавторства, семинаров и группы в Беркли, возглавляемой двумя сильнейшими специалистами по теории сложности в этой области. Его олимпиадный рекорд, хотя и отличный, включает 67-е место. Что можно сказать без преувеличения, так это более узкая и интересная вещь: он первоклассный профессионал в одном из самых технически сложных углов математики, и его определяющий результат закрыл вопрос, который был открыт годами. Это не то же самое, что гениальность, и он никогда на это не претендовал.

Перспективы

Карьера Манурангси имеет необычную форму для теоретика: доказательства невозможности были первыми, прикладная работа по конфиденциальности — второй. Переход к дифференциальной приватности и справедливому делению предполагает человека, который, установив, где находятся стены, теперь предпочел бы строить внутри них. Тренерская работа в тайской олимпиаде может оказаться более долговечным наследием — страна, которая однажды приняла IOI, теперь выращивает людей, которые его выигрывают.