<p>One example is the claimed proof of the Gilbert-Pollak conjecture on the Steiner ratio, which appears in <a href="https://doi.org/10.1109/FSCS.1990.89526" rel="noreferrer">FOCS'90</a>, and <a href="https://doi.org/10.1007/BF01758755" rel="noreferrer">Algorithmica</a>. The conjecture is <a href="https://doi.org/10.1007%2Fs00453-011-9508-3" rel="noreferrer">now considered open</a>.</p>

<p>Another examples include a sequence of <a href="http://dx.doi.org/10.1016/j.jcss.2010.06.002" rel="noreferrer">algorithms on graph embedding</a>.</p>

<p>There are more examples, but without similarly published refutations as above, it is difficulty to list due to the subtle nature.</p>

CC BY-SA 4.0
2020-05-30T14:08:01.170Z
2020-05-31T07:13:48.073Z
2020-05-31T07:13:48.073Z
Yixin Cao
<p>The very influential Karp, Vazirani, Vazirani <a href="https://people.eecs.berkeley.edu/~vazirani/pubs/online.pdf" rel="noreferrer">paper</a> on online bipartite matching turned out to have a mistake in one lemma (see <a href="https://cs.brown.edu/~claire/Publis/sigactnews08.pdf" rel="noreferrer">here</a> for details) that was only discovered close to two decades after the paper was first published. However, the mistake was indeed a fixable one. </p>

CC BY-SA 4.0
2020-05-31T07:08:07.053Z
This result also came to my mind when I answered. But I didn't list it because it has been fixed, and the main result "does not change very much."
Yixin Cao
CC BY-SA 4.0
2020-05-30T17:31:28.420Z
2020-05-30T17:31:28.420Z
gov
<p>There is some sort of "meta-flaw" pointed out by the following paper:</p>

<p>SOS is not obviously automatizable, even approximately. R. O'Donnell. ITCS '17.</p>

<p>Roughly speaking, it turns out that constant degree Sum-of-Square proofs cannot be generally approximated via current methods in polynomial time, contrary to the popular belief within the large body of SoS literature.</p>

CC BY-SA 4.0
2020-05-31T03:10:51.133Z
2020-05-31T03:10:51.133Z
Mahdi Cheraghchi
<p>A paper in STOC 1994 claimed a poly-time constant-factor approximation algorithm for finding balanced separators and some related problems, but the (incomplete) proofs in that paper are now considered flawed (e.g., see [2]).</p>

<p>[1] Chung and Yau. A near optimal algorithm for edge separators. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 1–8, 1994.</p>

<p>[2] Shmoys. 1996. <a href="https://scholar.google.com/scholar?cluster=11175298197389291534&amp;hl=en&amp;as_sdt=1,22" rel="noreferrer">Cut problems and their application to divide-and-conquer.</a> Approximation algorithms for NP-hard problems. PWS Publishing Co., USA, 192–235.</p>

CC BY-SA 4.0
2020-05-31T00:48:02.353Z
2020-05-31T00:48:02.353Z
Neal Young
<p>The famous paper </p>

<p>C. Papadimitriou and S. Vempala, <strong>On the Approximability of the Traveling Salesman Problem</strong>, in Proc. 32nd ACM STOC (2000), pp. 126–133, 2000</p>

<p>that claimed an inapproximability of 41/40 for symmetric TSP and 129/128 for asymmetric TSP had a flaw, which was fixed in the journal version 6 years later (claiming worse ratios of 117/116 and 220/219):</p>

<p>Papadimitriou, C.H., Vempala, S. On The Approximability Of The Traveling Salesman Problem. Combinatorica 26, 101–120 (2006). <a href="https://doi.org/10.1007/s00493-006-0008-z" rel="noreferrer">https://doi.org/10.1007/s00493-006-0008-z</a></p>

CC BY-SA 4.0
2020-05-31T03:01:22.627Z
2020-05-31T03:01:22.627Z
Mahdi Cheraghchi
<p>I am not sure this counts as "fundamental", but the following paper:
L. Fortnow. The Complexity of Perfect Zero-Knowledge. Advances in Computing Research (ed. S. Micali) Vol. 18 (1989) 
had a flaw pointed out here:
<a href="http://www.wisdom.weizmann.ac.il/~/oded/PSX/gop.pdf" rel="noreferrer">http://www.wisdom.weizmann.ac.il/~/oded/PSX/gop.pdf</a></p>

<p>Also, László Babai announced that he had fixed the error in his landmark graph isomorphism algorithm, as stated here: <a href="https://www.quantamagazine.org/graph-isomorphism-vanquished-again-20170114/" rel="noreferrer">https://www.quantamagazine.org/graph-isomorphism-vanquished-again-20170114/</a></p>

CC BY-SA 4.0
2020-05-30T22:34:51.557Z
2020-05-31T14:18:14.630Z
2020-05-31T14:18:14.630Z
Avi Tal
<p>I remember that the following was mentioned in a lecture on compiler construction I attended as a student.</p>
<p>The semi-unification problem (SUP) in the theory of programming languages is equivalent to type inference for <a href="https://en.wikipedia.org/wiki/Polymorphic_recursion" rel="nofollow noreferrer">polymorphic recursion</a>. Kfoury, Tiuryn and Urzyczyn proved that problem is undecidable in <a href="https://doi.org/10.1006/inco.1993.1003" rel="nofollow noreferrer">&quot;The Undecidability of the Semi-unification Problem&quot;</a>, Information and Computation Volume 102(1), pp. 83-101, 1993.</p>
<p>As they note,</p>
<blockquote>
<p>In this paper, we show that if the signature <span class="math-container">$\Sigma$</span> contains at least one function symbol of arity <span class="math-container">$\ge 2$</span>, then SUP is undecidable. [...] We have to admit, to our embarrassment, that among the many erroneous claims announcing the decidability of SUP, there was also ours [10].</p>
</blockquote>
<p>The quoted reference [10] is &quot;A Proper Extension of ML with an Effective Type-Assignment.&quot; POPL 1988: 58-69.</p>
<p>In this case, apparently several flawed decidability proofs were circulated, or possibly also published, before those authors finally got it right.</p>

CC BY-SA 4.0
2020-06-16T21:33:10.040Z
2020-06-27T21:33:17.467Z
2020-06-27T21:33:17.467Z
Hermann Gruber
<p>Actually in his famous paper <a href="https://www.cs.virginia.edu/%7Erobins/Turing_Paper_1936.pdf" rel="nofollow noreferrer">&quot;On Computable Numbers, with an Application to the Entscheidungsproblem.&quot;</a>, Turing made some errors, but in 1937 (one year after the publication) he
<a href="https://en.wikipedia.org/wiki/Turing%27s_proof#Complications" rel="nofollow noreferrer">corrected them</a>.</p>

CC BY-SA 4.0
2020-06-21T07:56:03.193Z
2020-06-21T07:56:03.193Z
greps
<p>In 1996 Agrawal and Arvind <a href="https://doi.org/10.1016/0304-3975(95)00073-9" rel="nofollow noreferrer">published a proof</a> that if SAT many-one reduces to a weighted linear threshold function, then <span class="math-container">$\mathsf{P}=\mathsf{NP}$</span>. A fatal flaw was subsequently found in a lemma (see story <a href="https://blog.computationalcomplexity.org/2009/10/thanks-for-fuzzy-memories.html" rel="nofollow noreferrer">here</a>). (This, in a line of work going back to Mahaney's Theorem on sparse NP-hard sets.)</p>
<p>In <a href="https://doi.org/10.1007/978-3-642-40313-2_23" rel="nofollow noreferrer">MFCS 2013, Buhrman, Fortnow, Hitchcock, and Loff</a> managed to recover a slightly weaker result: if SAT many-one reduces to a weighted linear threshold function then <span class="math-container">$\mathsf{PH}=\mathsf{P}^\mathsf{NP}$</span>.</p>
<p>As far as I know, the original claimed result is still an open question, as is finding an oracle where it is false (stated explicitly as open questions at the end of the MFCS '13 paper (ibid.)).</p>

CC BY-SA 4.0
2023-10-13T23:48:50.313Z
2023-10-13T23:48:50.313Z
Joshua Grochow
<p>There are a couple of interesting ones from PL Theory, where the stated results weren't wrong, per-say, but were widely interpreted to apply more broadly than they really did, or where clever &quot;workarounds&quot; were found later.</p>
<p>The two that stand out to me are:</p>
<ol>
<li><p>A self-normalizer for System-<span class="math-container">$F_\omega$</span>. The proven result was that you couldn't write an interpreter for <span class="math-container">$F_\omega$</span> in <span class="math-container">$F_\omega$</span>, due to a Godel-incompleteness style argument. But It was later shown that this only applies to <em>untyped</em> representations of <span class="math-container">$F_\omega$</span>. A self-interpreter is possible if you use a typed representation of terms, as was <a href="http://compilers.cs.ucla.edu/popl16/popl16-full.pdf" rel="nofollow noreferrer">shown later</a>.</p>
</li>
<li><p>Type-preserving continuation-passing style transformation of dependent types is impossible. This was <a href="https://dl.acm.org/doi/10.1145/503032.503043" rel="nofollow noreferrer">shown to be impossible</a>. But later, it was discovered that it was only impossible for their particular style of translation (the &quot;double negation&quot; translation). It was later shown that type-preserving CPS transformation is <a href="https://www.williamjbowman.com/resources/cps-sigma.pdf" rel="nofollow noreferrer">not not possible</a>.</p>
</li>
</ol>

CC BY-SA 4.0
2023-10-12T15:08:37.597Z
Note: "self-interpreter" does not mean what I would expect "self-normalizer" to mean. A self-interpreter is, given a quotation scheme $[-]$, a term $I$ that acts on quoted terms to give their value, i.e. $I[T] = T$. This does _not_ mean that there is a term $N$ that acts to give quoted normal forms $N[T] = [V]$ where $V$ is the normal form of $T$. In the referenced paper, there is no obvious way to get $N$ from $I$, since there is no internal way to quote $Q\ T = [T]$. And I think $N$ may be contradictory even if $I$ is not.
Dan Doel
CC BY-SA 4.0
2020-06-21T05:08:35.850Z
2020-06-23T10:09:18.733Z
2020-06-23T10:09:18.733Z
Joey Eremondi
<p>I am asking this question out of curiosity.</p>
<p>I recently encountered this well-known paper on (published in 2009):
<a href="https://link.springer.com/content/pdf/10.1007/s10994-009-5103-0.pdf" rel="nofollow noreferrer">the hardness of Euclidean kmeans</a></p>
<p>The paper showed that the previous NP-hardness result (<a href="https://www.cc.gatech.edu/%7Evempala/papers/dfkvv.pdf" rel="nofollow noreferrer">link</a>) for the Euclidean k-means (discovered in 2004 and a preliminary version appeared in 1999) was wrong. Note that after around 5 years somebody pointed out that the previously known result was incorrect.
They also mention that many of the well-known papers (like <a href="https://dl.acm.org/doi/pdf/10.5555/1283383.1283494" rel="nofollow noreferrer">kmeans++</a> paper) cited the incorrect hardness result till then.</p>
<p>Even when I read a paper, I find some minor mistakes. However, they are easily fixable and do not change the main result very much.</p>
<p>I want to ask if there had been any fundamental or highly cited paper, which was later found to be incorrect, and due to which the entire understanding of the field changed.</p>

CC BY-SA 4.0
2020-05-30T21:05:05.363Z
The answer to a similar question includes a few examples: https://cstheory.stackexchange.com/q/6253
Hermann Gruber
<soft-question>
Any fundamental papers in TCS which were found to be incorrect/wrong later?
Inuyasha Yagami
# Any fundamental papers in TCS which were found to be incorrect/wrong later?

(Asked by: username_0 on 2020-05-30)

I am asking this question out of curiosity.

I recently encountered this well-known paper on (published in 2009):
[the hardness of Euclidean kmeans](https://link.springer.com/content/pdf/10.1007/s10994-009-5103-0.pdf)

The paper showed that the previous NP-hardness result ([link](https://www.cc.gatech.edu/%7Evempala/papers/dfkvv.pdf)) for the Euclidean k-means (discovered in 2004 and a preliminary version appeared in 1999) was wrong. Note that after around 5 years somebody pointed out that the previously known result was incorrect.
They also mention that many of the well-known papers (like [kmeans++](https://dl.acm.org/doi/pdf/10.5555/1283383.1283494) paper) cited the incorrect hardness result till then.

Even when I read a paper, I find some minor mistakes. However, they are easily fixable and do not change the main result very much.

I want to ask if there had been any fundamental or highly cited paper, which was later found to be incorrect, and due to which the entire understanding of the field changed.

**Tags:** soft-question
> **Comments:**
> **username_1**: The answer to a similar question includes a few examples: https://cstheory.stackexchange.com/q/6253  

---

## 10 answers

### Answer by username_2 on 2020-05-30. Score: 22

One example is the claimed proof of the Gilbert-Pollak conjecture on the Steiner ratio, which appears in [FOCS'90](https://doi.org/10.1109/FSCS.1990.89526), and [Algorithmica](https://doi.org/10.1007/BF01758755). The conjecture is [now considered open](https://doi.org/10.1007%2Fs00453-011-9508-3).

Another examples include a sequence of [algorithms on graph embedding](http://dx.doi.org/10.1016/j.jcss.2010.06.002).

There are more examples, but without similarly published refutations as above, it is difficulty to list due to the subtle nature.


---

### Answer by username_3 on 2020-05-30. Score: 20

The very influential Karp, Vazirani, Vazirani [paper](https://people.eecs.berkeley.edu/~vazirani/pubs/online.pdf) on online bipartite matching turned out to have a mistake in one lemma (see [here](https://cs.brown.edu/~claire/Publis/sigactnews08.pdf) for details) that was only discovered close to two decades after the paper was first published. However, the mistake was indeed a fixable one.

> **Comments:**
> **username_2**: This result also came to my mind when I answered. But I didn't list it because it has been fixed, and the main result "does not change very much."  

---

### Answer by username_4 on 2020-05-31. Score: 16

There is some sort of "meta-flaw" pointed out by the following paper:

SOS is not obviously automatizable, even approximately. R. O'Donnell. ITCS '17.

Roughly speaking, it turns out that constant degree Sum-of-Square proofs cannot be generally approximated via current methods in polynomial time, contrary to the popular belief within the large body of SoS literature.


---

### Answer by username_5 on 2020-05-31. Score: 13

A paper in STOC 1994 claimed a poly-time constant-factor approximation algorithm for finding balanced separators and some related problems, but the (incomplete) proofs in that paper are now considered flawed (e.g., see [2]).

[1] Chung and Yau. A near optimal algorithm for edge separators. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 1–8, 1994.

[2] Shmoys. 1996. [Cut problems and their application to divide-and-conquer.](https://scholar.google.com/scholar?cluster=11175298197389291534&hl=en&as_sdt=1,22) Approximation algorithms for NP-hard problems. PWS Publishing Co., USA, 192–235.


---

### Answer by username_4 on 2020-05-31. Score: 12

The famous paper

C. Papadimitriou and S. Vempala, **On the Approximability of the Traveling Salesman Problem**, in Proc. 32nd ACM STOC (2000), pp. 126–133, 2000

that claimed an inapproximability of 41/40 for symmetric TSP and 129/128 for asymmetric TSP had a flaw, which was fixed in the journal version 6 years later (claiming worse ratios of 117/116 and 220/219):

Papadimitriou, C.H., Vempala, S. On The Approximability Of The Traveling Salesman Problem. Combinatorica 26, 101–120 (2006). <https://doi.org/10.1007/s00493-006-0008-z>


---

### Answer by username_6 on 2020-05-30. Score: 9

I am not sure this counts as "fundamental", but the following paper:
L. Fortnow. The Complexity of Perfect Zero-Knowledge. Advances in Computing Research (ed. S. Micali) Vol. 18 (1989)
had a flaw pointed out here:
<http://www.wisdom.weizmann.ac.il/~/oded/PSX/gop.pdf>

Also, László Babai announced that he had fixed the error in his landmark graph isomorphism algorithm, as stated here: <https://www.quantamagazine.org/graph-isomorphism-vanquished-again-20170114/>


---

### Answer by username_1 on 2020-06-16. Score: 4

I remember that the following was mentioned in a lecture on compiler construction I attended as a student.

The semi-unification problem (SUP) in the theory of programming languages is equivalent to type inference for [polymorphic recursion](https://en.wikipedia.org/wiki/Polymorphic_recursion). Kfoury, Tiuryn and Urzyczyn proved that problem is undecidable in ["The Undecidability of the Semi-unification Problem"](https://doi.org/10.1006/inco.1993.1003), Information and Computation Volume 102(1), pp. 83-101, 1993.

As they note,

> In this paper, we show that if the signature $\Sigma$ contains at least one function symbol of arity $\ge 2$, then SUP is undecidable. [...] We have to admit, to our embarrassment, that among the many erroneous claims announcing the decidability of SUP, there was also ours [10].

The quoted reference [10] is "A Proper Extension of ML with an Effective Type-Assignment." POPL 1988: 58-69.

In this case, apparently several flawed decidability proofs were circulated, or possibly also published, before those authors finally got it right.


---

### Answer by username_7 on 2020-06-21. Score: 3

Actually in his famous paper ["On Computable Numbers, with an Application to the Entscheidungsproblem."](https://www.cs.virginia.edu/%7Erobins/Turing_Paper_1936.pdf), Turing made some errors, but in 1937 (one year after the publication) he
[corrected them](https://en.wikipedia.org/wiki/Turing%27s_proof#Complications).


---

### Answer by username_8 on 2023-10-13. Score: 2

In 1996 Agrawal and Arvind [published a proof](https://doi.org/10.1016/0304-3975(95)00073-9) that if SAT many-one reduces to a weighted linear threshold function, then $\mathsf{P}=\mathsf{NP}$. A fatal flaw was subsequently found in a lemma (see story [here](https://blog.computationalcomplexity.org/2009/10/thanks-for-fuzzy-memories.html)). (This, in a line of work going back to Mahaney's Theorem on sparse NP-hard sets.)

In [MFCS 2013, Buhrman, Fortnow, Hitchcock, and Loff](https://doi.org/10.1007/978-3-642-40313-2_23) managed to recover a slightly weaker result: if SAT many-one reduces to a weighted linear threshold function then $\mathsf{PH}=\mathsf{P}^\mathsf{NP}$.

As far as I know, the original claimed result is still an open question, as is finding an oracle where it is false (stated explicitly as open questions at the end of the MFCS '13 paper (ibid.)).


---

### Answer by username_9 on 2020-06-21. Score: 2

There are a couple of interesting ones from PL Theory, where the stated results weren't wrong, per-say, but were widely interpreted to apply more broadly than they really did, or where clever "workarounds" were found later.

The two that stand out to me are:

1. A self-normalizer for System-$F\_\omega$. The proven result was that you couldn't write an interpreter for $F\_\omega$ in $F\_\omega$, due to a Godel-incompleteness style argument. But It was later shown that this only applies to *untyped* representations of $F\_\omega$. A self-interpreter is possible if you use a typed representation of terms, as was [shown later](http://compilers.cs.ucla.edu/popl16/popl16-full.pdf).
2. Type-preserving continuation-passing style transformation of dependent types is impossible. This was [shown to be impossible](https://dl.acm.org/doi/10.1145/503032.503043). But later, it was discovered that it was only impossible for their particular style of translation (the "double negation" translation). It was later shown that type-preserving CPS transformation is [not not possible](https://www.williamjbowman.com/resources/cps-sigma.pdf).

> **Comments:**
> **username_10**: Note: "self-interpreter" does not mean what I would expect "self-normalizer" to mean. A self-interpreter is, given a quotation scheme $[-]$, a term $I$ that acts on quoted terms to give their value, i.e. $I[T] = T$. This does _not_ mean that there is a term $N$ that acts to give quoted normal forms $N[T] = [V]$ where $V$ is the normal form of $T$. In the referenced paper, there is no obvious way to get $N$ from $I$, since there is no internal way to quote $Q\ T = [T]$. And I think $N$ may be contradictory even if $I$ is not.  

---

