We often hear about classic research and publications in the field of computational complexity (Turing, Cook, Karp, Hartmanis, Razborov etc). I was wondering if there are recently published papers considered seminal and a must read. By recent I mean in the last 5/10 years.
10 Answers
$\begingroup$
$\endgroup$
2
The recent paper of László Babai showing that Graph Isomorphism is in Quasi-P is already a classic.
Here is a more accessible exposition of the result published in the ICM 2018 proceedings.
-
3$\begingroup$ Is this paper considered fully vetted by the community? Laci's website still says that it's not fully peer reviewed, but his last update was over a year ago. $\endgroup$ Commented Jun 24, 2019 at 15:54
-
6$\begingroup$ @StellaBiderman We even have a separate question on that: cstheory.stackexchange.com/q/40353 . $\endgroup$ Commented Jun 24, 2019 at 16:11
$\begingroup$
$\endgroup$
In a recent preprint, Harvey and Van Der Hoeven show how to compute Integer multiplication in time $O(n \log n)$ on a multi-tape Turing machine, culminating some 60 years of research (Karatsuba, Toom–Cook, Schönhage–Strassen, Fürer, Harvey–Van Der Hoeven–Lecerf). The paper has not yet been peer-reviewed, but prior work of the authors on this problem makes it plausible, and experts seem to be optimistic.
$\begingroup$
$\endgroup$
2
Importance is in the eyes of the beholder. However, I would say that the Feder–Vardi CSP dichotomy conjecture, proved independently by A. Bulatov and D. Zhuk, is a seminal result.
-
2$\begingroup$ These are indeed important papers and definitely belong in this list, but they form the keystone in a large body of work. I'm not sure this achievement is going to open up many further areas for research (which I would expect from a "seminal" result). I think the seminal work here was the original Feder-Vardi paper. $\endgroup$ Commented Jun 29, 2019 at 8:36
-
1$\begingroup$ The OP uses a few different terms: "Most important", "Seminal", and "Must read". The proof of the dichotomy conjecture probably satisfies the first (it's a fascinating and powerful result!) but not the second (as you said, this proof itself will not substantially change how research is progressing) or third (the proof is sufficiently far removed from the implications of the conjecture, as to be likely be uninteresting unless you're already in that subfield.) $\endgroup$ Commented Jul 2, 2019 at 20:33
$\begingroup$
$\endgroup$
1
Non-Uniform ACC Circuit Lower Bounds by Ryan Williams:
https://people.csail.mit.edu/rrw/acc-lbs.pdf
and Classical Verification of Quantum Computations by Urmila Mahadev:
http://ieee-focs.org/FOCS-2018-Papers/pdfs/59f259.pdf
seem like good candidates
$\begingroup$
$\endgroup$
2
This new paper by Hao Huang [1] (not yet peer-reviewed, as far as I know) probably qualifies... it proves the sensitivity conjecture of Nisan and Szegedy, which has been open for ~30 years.
[1] Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, Hao Huang. Manuscript, 2019. https://arxiv.org/abs/1907.00847
-
3$\begingroup$ While the paper hasn’t been officially peer reviewed, it’s pretty clearly right. It’s one of the best examples of a “NP” proof that’s incredibly easy to verify and quite hard to come up with. $\endgroup$ Commented Jul 5, 2019 at 16:26
-
2$\begingroup$ @StellaBiderman I know, and agree. But it's still an important thing to state, as peer-review is more or less the currency we base our system on. $\endgroup$ Commented Jul 5, 2019 at 17:04
$\begingroup$
$\endgroup$
Subhash Khot, Dor Minzer and Muli Safra's 2018 work "Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion" has gotten us "half way" to the Unique Games Conjecture and is methodologically quite interesting according to people more knowledgeable than I. Quoting Boaz Barak,
This establishes for the first time hardness of unique games in the regime for which a sub-exponential time algorithm was known, and hence (necessarily) uses a reduction with some (large) polynomial blowup. While it is theoretically still possible for the unique games conjecture to be false (as I personally believed would be the case until this latest sequence of results) the most likely scenario is now that the UGC is true, and the complexity of the UG(s,c) problem looks something like the following...
The paper has caused some researchers (including Barak) to publicly change their opinion on the truth of the UGC (from false to true).
$\begingroup$
$\endgroup$
"On the possibility of faster SAT algorithms" by Pătraşcu & Williams (SODA 2010). It gives tight relations between the complexity of solving CNF-SAT and the complexity of some polynomial problems (k-dominating set, d-sum, etc.).
The results are twofold: either we can improve the complexity of solving some polynomial problems, and thus ETH is false and we get a better algorithm for CNF-SAT. Or ETH is true, and thus we get lower bounds on several polynomial problems.
The paper is surprisingly easy to read and to understand. For me, it's the actual start of fine-grained complexity.
$\begingroup$
$\endgroup$
0
It’s one year beyond the 10-year limit, but “Delegating Computation: Interactive Proofs for Muggles” by Goldwasser, Kalai, and Rothblum has been a hugely influential paper. The main result is that there is an interactive proof for any log-space uniform computation where the prover runs in time poly(n) and the verifier in time n*polylog(n) with polylog(n) bits of communication.
The paper has jump-started research on interactive proofs and verifiable computation for problems in P has been incredibly influential in cryptography where it and the work that followed has had make real-world interactive proofs nearly practical.
$\begingroup$
$\endgroup$
For impact, and reach landmark paper by Indyk, and Backurs giving limits to edit distance computation. This paper shows limits to computing, by linking, k-SAT, and SETH. To limit computing the levenshtein distance, between strings, the paper shows tight bounds to computing the edit distance- any better then SETH is violated (SETH may be false in the first place, or even have tighter lower bounds though). The applicability of SETH to possibly problems in P, for getting bounds, or limiting application of algorithms (possibly computation!) is new.
Or this paper by P. Goldberg, and C. Papadimitrou, about a uniform complexity for total functions Towards a unified complexity theory of total functions.
$\begingroup$
$\endgroup$
Not sure if this qualifies -- it's both more than 10 years old, and not really a computational complexity result in itself -- but I think the pair of {Graph Structure Theorem, Graph Minor Theorem} is worth noting. It was completed in 2004, and establishes an equivalence between "Bounded topological complexity" and "Does not contain some finite set of minors". Each theorem establishes one direction of the equivalence.
This has primarily had an impact within the realm of parameterized complexity theory, where one of these measures is often bounded, allowing for efficient algorithms that leverage the other. So, I would say that these results have had substantial impact on computational complexity, even if they do not come directly from that field themselves.