<p>The recent <a href="https://arxiv.org/abs/1512.03547" rel="noreferrer">paper</a> of László Babai showing that Graph Isomorphism is in Quasi-P is already a classic.</p>

<p><a href="https://eta.impa.br/dl/109.pdf" rel="noreferrer">Here</a> is a more accessible exposition of the result published in the ICM 2018 proceedings.</p>

CC BY-SA 4.0
2019-06-24T15:54:31.060Z
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.
Stella Biderman
CC BY-SA 4.0
2019-06-24T16:11:13.493Z
@StellaBiderman We even have a separate question on that: https://cstheory.stackexchange.com/q/40353 .
Emil Jeřábek
CC BY-SA 4.0
2019-06-24T13:55:54.203Z
2019-06-25T14:15:03.597Z
2019-06-25T14:15:03.597Z
Denis
<p>Importance is in the eyes of the beholder. However, I would say that the Feder–Vardi CSP dichotomy conjecture, proved independently by <a href="https://arxiv.org/abs/1703.03021" rel="noreferrer">A. Bulatov</a> and <a href="https://arxiv.org/abs/1704.01914" rel="noreferrer">D. Zhuk</a>, is a seminal result.</p>

CC BY-SA 4.0
2019-06-29T08:36:09.740Z
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.
András Salamon
CC BY-SA 4.0
2019-07-02T20:33:32.160Z
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.)
Alex Meiburg
CC BY-SA 4.0
2019-06-24T11:17:58.600Z
2019-06-24T11:17:58.600Z
Emil Jeřábek
<p>Non-Uniform ACC Circuit Lower Bounds by Ryan Williams:</p>

<p><a href="https://people.csail.mit.edu/rrw/acc-lbs.pdf" rel="noreferrer">https://people.csail.mit.edu/rrw/acc-lbs.pdf</a></p>

<p>and Classical Verification of Quantum Computations by Urmila Mahadev:</p>

<p><a href="http://ieee-focs.org/FOCS-2018-Papers/pdfs/59f259.pdf" rel="noreferrer">http://ieee-focs.org/FOCS-2018-Papers/pdfs/59f259.pdf</a></p>

<p>seem like good candidates</p>

CC BY-SA 4.0
2024-06-04T19:18:46.650Z
Thanks allot! Excellent proof.
Avi Tal
CC BY-SA 4.0
2019-06-24T22:43:32.603Z
2019-06-24T22:43:32.603Z
Avi Tal
<p>This new paper by Hao Huang [1] (not yet peer-reviewed, as far as I know) <em>probably</em> qualifies... it proves the sensitivity conjecture of Nisan and Szegedy, which has been open for ~30 years.</p>

<p>[1] <em>Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture,</em> Hao Huang. Manuscript, 2019. <a href="https://arxiv.org/abs/1907.00847" rel="noreferrer">https://arxiv.org/abs/1907.00847</a></p>

CC BY-SA 4.0
2019-07-05T16:26:02.457Z
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.
Stella Biderman
CC BY-SA 4.0
2019-07-05T17:04:12.667Z
@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.
Clement C.
CC BY-SA 4.0
2019-07-02T01:19:57.417Z
2019-07-02T20:23:30.897Z
2019-07-02T20:23:30.897Z
Clement C.
<p>In a recent preprint, Harvey and Van Der Hoeven show how to compute <a href="https://hal.archives-ouvertes.fr/hal-02070778/" rel="noreferrer">Integer multiplication in time <span class="math-container">$O(n \log n)$</span></a> 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.</p>

CC BY-SA 4.0
2019-06-25T14:55:05.010Z
2019-06-25T14:55:05.010Z
Emil Jeřábek
<p>"On the possibility of faster SAT algorithms" by Pătraşcu &amp; 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.). </p>

<p>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. </p>

<p>The paper is surprisingly easy to read and to understand. For me, it's the actual start of fine-grained complexity.</p>

CC BY-SA 4.0
2019-06-26T11:30:14.353Z
2019-06-26T11:30:14.353Z
Lamine
<p>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.</p>

<p>The paper has jump-started research on interactive proofs and verifiable computation for problems in <strong>P</strong> has been incredibly influential in cryptography where it and the work that followed has had make real-world interactive proofs nearly practical.</p>

CC BY-SA 4.0
2019-06-24T12:34:16.220Z
2019-10-25T18:57:49.597Z
2019-10-25T18:57:49.597Z
Stella Biderman
<p>Subhash Khot, Dor Minzer and Muli Safra's 2018 work "Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion" has gotten us <a href="https://windowsontheory.org/2018/01/10/unique-games-conjecture-halfway-there/" rel="nofollow noreferrer">"half way"</a> to the Unique Games Conjecture and is methodologically quite interesting according to people more knowledgeable than I. Quoting Boaz Barak,</p>

<blockquote>
  <p>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...</p>
</blockquote>

<p>The paper has caused some researchers (including Barak) to publicly change their opinion on the truth of the UGC (from false to true).</p>

CC BY-SA 4.0
2019-06-25T19:46:26.703Z
2019-10-25T18:53:19.267Z
2019-10-25T18:53:19.267Z
Stella Biderman
<p>For impact, and reach landmark paper by <a href="https://arxiv.org/abs/1412.0348" rel="nofollow noreferrer">Indyk, and Backurs</a> 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 <a href="https://arxiv.org/abs/1511.06022" rel="nofollow noreferrer">even have tighter lower bounds</a> though). The applicability of SETH to possibly problems in P, for getting bounds, or limiting application of algorithms (possibly computation!) is new. </p>

<p>Or this paper by P. Goldberg, and C. Papadimitrou, about a uniform complexity for total functions 
<a href="https://www.sciencedirect.com/science/article/pii/S0022000017302878" rel="nofollow noreferrer">Towards a unified complexity theory of total functions</a>. </p>

CC BY-SA 4.0
2019-06-26T08:13:36.380Z
2019-06-26T08:36:45.773Z
2019-06-26T08:36:45.773Z
user3483902
<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2019-07-02T20:40:57.680Z
2019-07-02T20:40:57.680Z
Alex Meiburg
<p>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. </p>

<cc.complexity-theory><big-list>
Most important new papers in computational complexity
Yamar69
# Most important new papers in computational complexity

(Asked by: username_0 on 2019-06-24)

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.

**Tags:** cc.complexity-theory, big-list


---

## 10 answers

### Answer by username_1 on 2019-06-24. Score: 29

The recent [paper](https://arxiv.org/abs/1512.03547) of László Babai showing that Graph Isomorphism is in Quasi-P is already a classic.

[Here](https://eta.impa.br/dl/109.pdf) is a more accessible exposition of the result published in the ICM 2018 proceedings.

> **Comments:**
> **username_2**: 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.  
> **username_3**: @StellaBiderman We even have a separate question on that: https://cstheory.stackexchange.com/q/40353 .  

---

### Answer by username_3 on 2019-06-25. Score: 26

In a recent preprint, Harvey and Van Der Hoeven show how to compute [Integer multiplication in time $O(n \log n)$](https://hal.archives-ouvertes.fr/hal-02070778/) 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.


---

### Answer by username_3 on 2019-06-24. Score: 22

Importance is in the eyes of the beholder. However, I would say that the Feder–Vardi CSP dichotomy conjecture, proved independently by [A. Bulatov](https://arxiv.org/abs/1703.03021) and [D. Zhuk](https://arxiv.org/abs/1704.01914), is a seminal result.

> **Comments:**
> **username_4**: 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.  
> **username_5**: 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.)  

---

### Answer by username_6 on 2019-06-24. Score: 20

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

> **Comments:**
> **username_6**: Thanks allot! Excellent proof.  

---

### Answer by username_7 on 2019-07-02. Score: 16

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>

> **Comments:**
> **username_2**: 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.  
> **username_7**: @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.  

---

### Answer by username_2 on 2019-06-25. Score: 15

Subhash Khot, Dor Minzer and Muli Safra's 2018 work "Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion" has gotten us ["half way"](https://windowsontheory.org/2018/01/10/unique-games-conjecture-halfway-there/) 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).


---

### Answer by username_8 on 2019-06-26. Score: 14

"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.


---

### Answer by username_2 on 2019-06-24. Score: 11

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.


---

### Answer by username_9 on 2019-06-26. Score: 4

For impact, and reach landmark paper by [Indyk, and Backurs](https://arxiv.org/abs/1412.0348) 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](https://arxiv.org/abs/1511.06022) 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](https://www.sciencedirect.com/science/article/pii/S0022000017302878).


---

### Answer by username_5 on 2019-07-02. Score: 2

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.


---

