35

I am asking this question out of curiosity.

I recently encountered this well-known paper on (published in 2009): the hardness of Euclidean kmeans

The paper showed that the previous NP-hardness result (link) 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++ 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.

isaacg
  • 806
  • 6
  • 14
Inuyasha Yagami
  • 1,531
  • 1
  • 8
  • 25

10 Answers10

22

One example is the claimed proof of the Gilbert-Pollak conjecture on the Steiner ratio, which appears in FOCS'90, and Algorithmica. The conjecture is now considered open.

Another examples include a sequence of algorithms on graph embedding.

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

Yixin Cao
  • 2,560
  • 1
  • 16
  • 29
20

The very influential Karp, Vazirani, Vazirani paper on online bipartite matching turned out to have a mistake in one lemma (see here for details) that was only discovered close to two decades after the paper was first published. However, the mistake was indeed a fixable one.

gov
  • 341
  • 1
  • 11
  • 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." – Yixin Cao May 31 '20 at 07:08
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.

Mahdi Cheraghchi
  • 4,031
  • 22
  • 30
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. Approximation algorithms for NP-hard problems. PWS Publishing Co., USA, 192–235.

Neal Young
  • 10,546
  • 33
  • 60
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

Mahdi Cheraghchi
  • 4,031
  • 22
  • 30
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/

Avi Tal
  • 1,606
  • 1
  • 8
  • 13
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. Kfoury, Tiuryn and Urzyczyn proved that problem is undecidable in "The Undecidability of the Semi-unification Problem", 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.

Hermann Gruber
  • 6,470
  • 1
  • 35
  • 58
3

Actually in his famous paper "On Computable Numbers, with an Application to the Entscheidungsproblem.", Turing made some errors, but in 1937 (one year after the publication) he corrected them.

greps
  • 157
  • 6
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.

  2. Type-preserving continuation-passing style transformation of dependent types is impossible. This was shown to be impossible. 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.

Hermann Gruber
  • 6,470
  • 1
  • 35
  • 58
Joey Eremondi
  • 2,832
  • 15
  • 29
  • 2
    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 Oct 12 '23 at 15:08
2

In 1996 Agrawal and Arvind published a proof 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). (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 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.)).

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228