Самые важные новые статьи в вычислительной сложности

Мы часто слышим о классических исследованиях и публикациях в области вычислительной сложности (Тьюринг, Кук, Карп, Хартманис, Разборов и др.). Мне было интересно, есть ли недавно опубликованные статьи, которые считаются основополагающими и должны быть прочитаны. Под недавним я имею в виду последние 5/10 лет.

Недавняя статья Ласло Бабая, показывающая, что изоморфизм графов находится в квази-П, уже является классикой.

Вот более доступное изложение результатов, опубликованных в материалах ICM 2018.

В недавнем препринте Харви и Ван Дер Хувен показывают, как вычислить целочисленное умножение во времени $O(n \log n)$ на многоленточной машине Тьюринга, что привело к 60-летним исследованиям (Карацуба, Тоом – Кук, Шёнхаге-Штрассен, Фюрер). Харви-Ван-дер-Хувен-Лесерф). Документ еще не был рецензирован, но предыдущая работа авторов по этой проблеме делает его правдоподобным, и эксперты, похоже, настроены оптимистично.

Важность в глазах смотрящего. Однако я бы сказал, что гипотеза о дихотомии CSP Федера – Варди, доказанная независимо А. Булатовым и Д. Жуком , является плодотворным результатом.

Неравномерная нижняя граница цепи ACC Райана Уильямса:

https://people.csail.mit.edu/rrw/acc-lbs.pdf

и классическая проверка квантовых вычислений Урмила Махадева:

http://ieee-focs.org/FOCS-2018-Papers/pdfs/59f259.pdf

кажутся хорошими кандидатами

Эта новая статья Хао Хуанга [1] (насколько я знаю, еще не рецензированная), вероятно, отвечает требованиям ... она доказывает гипотезу чувствительности Нисана и Сегеди, которая была открыта в течение ~ 30 лет.

[1] Индуцированные подграфы гиперкубов и доказательство гипотезы о чувствительности, Хао Хуан. Рукопись, 2019. https://arxiv.org/abs/1907.00847

Субхаш Хот, Дор Минзер и Мули Сафра, опубликованные в 2018 году «Псевдослучайные множества в графе Грассмана, имеют почти идеальное расширение», сделали нас «на полпути» к предположению об уникальных играх и методологически довольно интересны для людей, более знающих, чем я. Цитата Боаз Барак ,

Это впервые устанавливает жесткость уникальных игр в режиме, для которого был известен субэкспоненциальный алгоритм времени, и, следовательно, (обязательно) использует редукцию с некоторым (большим) полиномиальным взрывом. Хотя теоретически все еще возможно, что гипотеза об уникальных играх будет ложной (как я лично полагал, будет иметь место до этой последней последовательности результатов), наиболее вероятным сценарием является то, что UGC верна, и сложность UG (s) в) проблема выглядит примерно так ...

Этот документ заставил некоторых исследователей (включая Барака) публично изменить свое мнение об истине UGC (с ложного на истинное).

«О возможности более быстрых алгоритмов SAT». Автор: Pătraşcu & Williams (SODA 2010). Это дает тесную связь между сложностью решения CNF-SAT и сложностью некоторых полиномиальных задач (k-доминирующее множество, d-сумма и т. Д.).

Результаты имеют два аспекта: либо мы можем улучшить сложность решения некоторых полиномиальных задач, и, следовательно, ETH неверен, и мы получаем лучший алгоритм для CNF-SAT. Или ETH верно, и, таким образом, мы получаем нижние оценки для нескольких полиномиальных задач.

Документ на удивление легко читать и понимать. Для меня это фактическое начало мелкозернистой сложности.

Это один год после 10-летнего лимита, но «Делегирование вычислений: интерактивные доказательства для магглов» Голдвассера, Калаи и Ротблюма было чрезвычайно влиятельным документом. Основным результатом является то, что существует интерактивное доказательство для любых равномерных вычислений в лог-пространстве, когда проверяющий работает во времени poly (n), а верификатор - во времени n * polylog (n) с битами polylog (n) связи.

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

Для удара и достижения ориентир бумаги Indyk, а Backurs дает ограничения для редактирования расчета расстояния. Эта статья показывает ограничения для вычислений, связывая, k-SAT и SETH. Чтобы ограничить вычисление расстояния Левенштейна между строками, в статье показаны жесткие границы для вычисления расстояния редактирования - лучше, чем нарушается SETH (SETH может быть ложным в первую очередь или даже иметь более жесткие нижние границы ). Применимость SETH к возможным проблемам в P, для получения границ или ограничения применения алгоритмов (возможно, вычисления!) Является новой.

Или эта статья П. Голдберга и С. Пападимитру о равномерной сложности для полных функций На пути к единой теории сложности полных функций .

Не уверен, имеет ли это право - ему более 10 лет, и он сам по себе не является результатом вычислительной сложности, но я думаю, что пара {Теорема о структуре графа, Теорема о малом графе} стоит отметить. Он был завершен в 2004 году и устанавливает эквивалентность между «Ограниченной топологической сложностью» и «Не содержит некоторого конечного множества миноров». Каждая теорема устанавливает одно направление эквивалентности.

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