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

34

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

Yamar69
источник

Ответы:

28

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

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

Денис
источник
3
Считается ли этот документ полностью проверенным сообществом? На сайте Laci все еще говорится, что он не полностью проверен, но его последнее обновление было более года назад.
Стелла Бидерман
6
@StellaBiderman У нас даже есть отдельный вопрос по этому поводу : cstheory.stackexchange.com/q/40353 .
Эмиль Йержабек поддерживает Монику
25

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

Эмиль Йержабек поддерживает Монику
источник
22

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

Эмиль Йержабек поддерживает Монику
источник
2
Это действительно важные документы, которые однозначно входят в этот список, но они составляют основу большой работы. Я не уверен, что это достижение откроет много других областей для исследования (что я ожидаю от "оригинального" результата). Я думаю, что оригинальной работой здесь была оригинальная статья Федера-Варди.
Андрас Саламон
1
ОП использует несколько разных терминов: «Самый важный», «Основной» и «Должен прочитать». Доказательство гипотезы о дихотомии, вероятно, удовлетворяет первому (это увлекательный и мощный результат!), Но не второму (как вы сказали, само это доказательство существенно не изменит ход исследований) или третьему (доказательство достаточно далеко отстает от последствия предположения, которые могут быть неинтересными, если вы уже не в этом подполе.)
Алекс Мейбург
16

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

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

Клемент С.
источник
2
Хотя статья официально не прошла рецензирование, она совершенно точно права. Это один из лучших примеров доказательства «NP», которое невероятно легко проверить и с которым довольно сложно придумать.
Стелла Бидерман
2
@StellaBiderman Я знаю, и согласен. Но это все же важно заявить, так как рецензирование - более или менее валюта, на которой мы основываем нашу систему.
Клемент С.
14

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

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

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

Стелла Бидерман
источник
13

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

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

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

Ламин
источник
9

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

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

Стелла Бидерман
источник
@ Сашо, я не согласен. Однако эта статья вообще не касается оптимизации времени выполнения. Тот факт , что в реальном мире , он работает гораздо гораздо быстрее , чем предыдущие подходы является преимуществом, но не является главным в работе (а не на самом деле измеряется авторами на всех). Это ФСК , потому что он смотрит на проверки мощности испытателей слабее , чем P .
Стелла Бидерман
4

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

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

user3483902
источник
2

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

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

Алекс Мейбург
источник