Najważniejsze nowe artykuły w złożoności obliczeniowej

Często słyszymy o klasycznych badaniach i publikacjach z zakresu złożoności obliczeniowej (Turing, Cook, Karp, Hartmanis, Razborov itp.). Zastanawiałem się, czy są ostatnio opublikowane artykuły uważane za przełomowe i konieczne do przeczytania. Mam na myśli ostatnie 5/10 lat.

Niedawny artykuł László Babai pokazujący, że izomorfizm grafów występuje w quasi-P, jest już klasyką.

Oto bardziej dostępna ekspozycja wyniku opublikowana w postępowaniu ICM 2018.

$O(n \log n)$

Znaczenie ma w oczach patrzącego. Powiedziałbym jednak, że hipoteza dychotomii Feder-Vardi CSP, udowodniona niezależnie przez A. Bulatova i D. Zhuka , jest przełomowym rezultatem.

Ryan Williams: niejednolity obwód ACC w dolnych granicach:

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

i klasyczna weryfikacja obliczeń kwantowych przez Urmila Mahadev:

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

wydają się dobrymi kandydatami

Ten nowy artykuł Hao Huanga [1] (o ile nie jestem recenzowany, o ile wiem) prawdopodobnie kwalifikuje ... dowodzi wrażliwości hipotezy Nisana i Szegedy, otwartej od około 30 lat.

[1] Indukowane podgrupy hipersześcianów i dowód hipotezy wrażliwości, Hao Huang. Rękopis, 2019. https://arxiv.org/abs/1907.00847

Praca Subhash Khot, Dor Minzer i Muli Safra 2018 „Zestawy pseudolosowe w grafice Grassmanna mają prawie idealną ekspansję” dostarczyła nas „w połowie drogi” do wyjątkowej gry hipotetycznej i jest metodologicznie dość interesująca według osób bardziej kompetentnych niż I. Cytowanie Boaz Barak ,

Ustanawia to po raz pierwszy twardość unikalnych gier w reżimie, dla których znany jest algorytm subwykładniczy, i stąd (koniecznie) wykorzystuje redukcję z pewnym (dużym) wielomianowym powiększeniem. Chociaż teoretycznie nadal możliwe jest, że unikalne przypuszczenie dotyczące gier jest fałszywe (jak osobiście uważałem, że tak będzie do ostatniej sekwencji wyników), najbardziej prawdopodobnym scenariuszem jest teraz, że UGC jest prawdziwe, a złożoność UG (s) , c) problem wygląda mniej więcej tak:

Artykuł spowodował, że niektórzy badacze (w tym Barak) publicznie zmienili swoje zdanie na temat prawdy UGC (z fałszywej na prawdziwą).

„O możliwości szybszych algorytmów SAT” Pătraşcu & Williams (SODA 2010). Daje ścisłe związki między złożonością rozwiązywania CNF-SAT a złożonością niektórych problemów wielomianowych (zbiór dominujący k, suma d itp.).

Wyniki są dwojakie: albo możemy poprawić złożoność rozwiązania niektórych problemów wielomianowych, a zatem ETH jest fałszywe i otrzymujemy lepszy algorytm dla CNF-SAT. Albo ETH jest prawdą, a zatem uzyskujemy niższe granice dla kilku problemów wielomianowych.

Artykuł jest zaskakująco łatwy do odczytania i zrozumienia. Dla mnie jest to faktyczny początek drobnoziarnistej złożoności.

Jest to rok powyżej 10-letniego limitu, ale „Delegowanie obliczeń: interaktywne dowody dla mugoli” autorstwa Goldwassera, Kalai i Rothbluma było niezwykle wpływowym pismem. Głównym rezultatem jest to, że istnieje interaktywny dowód na dowolne obliczenie jednolitego obszaru logów, w którym sprawdzanie działa w czasie poli (n), a weryfikator w czasie n * polilog (n) z polilogiem (n) bitami komunikacji.

W artykule rozpoczęto skrupulatne badania nad dowodami interaktywnymi, a weryfikowalne obliczenia problemów w P miały niewiarygodny wpływ na kryptografię, w której wraz z następującymi pracami sprawiły, że rzeczywiste dowody interaktywne stały się praktycznie praktyczne.

Uderzaj i docieraj do przełomowych artykułów Indyk, a Backurs podaje limity edycji obliczeń odległości. W tym artykule przedstawiono ograniczenia przetwarzania, poprzez linkowanie, k-SAT i SETH. Aby ograniczyć obliczanie odległości levenshteina, między ciągami, papier pokazuje ścisłe granice obliczania odległości edycji - lepiej niż SETH jest naruszone (SETH może być fałszywe w pierwszej kolejności, a nawet mieć mocniejsze dolne granice ). Możliwość zastosowania SETH do ewentualnych problemów w P, do uzyskania granic lub ograniczenia zastosowania algorytmów (być może obliczeń!) Jest nowa.

Lub ten artykuł P. Goldberga i C. Papadimitrou, o jednolitej złożoności dla funkcji całkowitych W kierunku jednolitej teorii złożoności funkcji całkowitych .

Nie jestem pewien, czy to się kwalifikuje - ma on ponad 10 lat i nie jest tak naprawdę złożonością obliczeniową - ale myślę, że warto zwrócić uwagę na parę {Twierdzenie o strukturze wykresu, Twierdzenie o mniejszym wykresie}. Został ukończony w 2004 r. I ustanawia równoważność między „Ograniczoną złożonością topologiczną” a „Nie zawiera pewnego skończonego zestawu małoletnich”. Każde twierdzenie ustanawia jeden kierunek równoważności.

Wpłynęło to przede wszystkim na sferę sparametryzowanej teorii złożoności, gdzie jedna z tych miar jest często ograniczona, umożliwiając wydajne algorytmy, które wykorzystują drugą. Powiedziałbym więc, że wyniki te miały znaczący wpływ na złożoność obliczeniową, nawet jeśli same nie pochodzą bezpośrednio z tej dziedziny.