26
$\begingroup$

This is my first question on the cstheory stack, so don't be too rude if I'm violating etiquette somehow )

As we know, in mathematics even famous mathematicians, superstars and geniuses are doing serious mistakes time to time. For example, both 4-color theorem and Fermat theorem provide us dramatic cases of how even brightest minds can be deluded. It even can take years to prove the incorrectness of some falsy proofs.

My question is - can you provide some outstanding examples of such mistakes in computer science? I don't know, something like "Dr. X has proved in 1972 that it is impossible to do Y in less than O(log n) time, but in 1995 it turned out that he actually was wrong".

Improve this question
$\endgroup$
10
  • 13
    $\begingroup$ Not an outstanding example: algorithm for on-line bipartite matching by Karp, Vazirani & Vazirani (1990) had a mistake in one lemma that was discovered about 15 years later. $\endgroup$ – Jagadish Aug 15 '11 at 17:24
  • 2
    $\begingroup$ @shabunc these kinds of questions are asking for a list of answers, and so the community-wiki tag is appropriate for it. $\endgroup$ – Suresh Venkat Aug 15 '11 at 18:47
  • 4
    $\begingroup$ also, this question is related: cstheory.stackexchange.com/questions/3616/… $\endgroup$ – Suresh Venkat Aug 15 '11 at 18:48
  • 2
    $\begingroup$ If asking about errors is impolite, your question itself is impolite and avoiding the word “errors” in the title is not a solution. $\endgroup$ – Tsuyoshi Ito Aug 16 '11 at 14:40
  • 3
    $\begingroup$ Relevant blog post Math Is Like The Stock Market. $\endgroup$ – Pratik Deoghare Aug 18 '11 at 18:17
28
$\begingroup$

An infamous example in computational geometry is the incorrect proof of the Zone Theorem for hyperplane arrangements published by Edelsbrunner, O'Rourke, and Seidel [FOCS 1983, SICOMP 1986]. The proof also appears in Edelsbrunner's 1987 computational geometry textbook.

Zone Theorem: In any arrangement of $n$ hyperplanes in $\mathbb{R}^d$, the total complexity of all cells intersecting any hyperplane is $O(n^{d-1})$.

The Zone Theorem is a key step in the proof that the standard recursive incremental algorithm to build an arrangement of $n$ hyperplanes in $\mathbb{R}^d$ runs in $O(n^d)$ time.

In 1990, Raimund Seidel discovered that the published proof was incorrect, after being challenged on a subtle technical point by a student in his computational geometry class. Meanwhile, a huge literature on hyperplane/halfspace/simplex/semialgebraic range searching had been developed, all of which relied on the $O(n^d)$ construction time for arrangements, which in turn relied on the Zone Theorem. (None of those authors noticed the bug. Raimund had taught the published "proof" in detail for several years before he was challenged.)

Fortunately, Edelsbrunner, Seidel, and Sharir almost immediately found a correct (and much simpler!) proof of the Zone Theorem [New Results and New Trends in CS 1991, SICOMP 1993].

Improve this answer
$\endgroup$
3
  • $\begingroup$ @JɛffE, this one is great example, thank you! $\endgroup$ – shabunc Aug 18 '11 at 13:42
  • 4
    $\begingroup$ Do you happen to know who the clever student was ? $\endgroup$ – Suresh Venkat Aug 19 '11 at 0:08
  • 4
    $\begingroup$ No, I don't. Raimund told me the story >15 years ago, when I was at Berkeley; if he told me the student's name, I've long since forgotten. (And probably so has Raimund.) The SICOMP 1993 paper doesn't mention the student either. $\endgroup$ – Jeffε Aug 19 '11 at 6:23
10
$\begingroup$

The Needham-Shroeder public key cryptography protocol, a 5-line protocol, has been shown insecure 17 years after its publication. This is the favorite example of Verification people for doing formal analysis of crypto protocols.

Improve this answer
$\endgroup$
3
  • 8
    $\begingroup$ Unless the original paper gives a wrong proof that the protocol is secure, this doesn't count as an error. Showing that proposed cryptosystems are insecure is in fact a part of research in crypto. $\endgroup$ – Mahdi Cheraghchi Aug 16 '11 at 18:34
  • 1
    $\begingroup$ agree with MCH, crypto protocols are subtle different story. $\endgroup$ – shabunc Aug 16 '11 at 18:37
  • 6
    $\begingroup$ There are two different concepts in this protocol: the encryption scheme and the communication protocol. The author were aware that there could be attacks on the encryption scheme, but they discussed the security of the communication protocol and conclude it is secure: "We assume that an intruder can interpose a computer in all communication paths, and thus can alter or copy parts of messages, replay messages, or emit false material. While this may seem an extreme view, it is the only safe one when designing authentication protocols" And the attack is of type man-in-the-middle. $\endgroup$ – Loïck Aug 18 '11 at 15:35
9
$\begingroup$

Dick Lipton has a new post out on the non-monotonicity of mathematical knowledge, and in it he documents examples of claims made that turned out to be false, or at least needed fixing.

Improve this answer
$\endgroup$
8
$\begingroup$

There have been conjectures that turned out to be false (e.g., constant-distortion embedding of negative type metrics disproved by Khot and Vishnoi), but there's nothing wrong with posing a false conjecture since after all it's a conjecture.

An example of an actual confusion, which didn't last long though, is parallel repetition. It was initially believed that for an interactive protocol with error probability $\epsilon$, the error reduces to $\epsilon^k$ for $k$ parallel repetitions. This claim turned out to be false, and in fact attempts to better understand parallel repetition turned out to open door to a great deal of beautiful mathematics.

It's also believed that Feynman had thought it obvious that $\mathsf{P} \neq \mathsf{NP}$ (or maybe that quantum mechanics obviously can't be simulated efficiently by classical computers). But then he wasn't a theoretical computer scientist nor is anybody sure of the accuracy of this story.

Improve this answer
$\endgroup$
6
  • $\begingroup$ +1 for Feynman. Can you provide more details about Feynman and P vs NP? $\endgroup$ – becko Aug 16 '11 at 1:57
  • 2
    $\begingroup$ Ask Scott Aaronson, he knows this stuff well. $\endgroup$ – Mahdi Cheraghchi Aug 16 '11 at 2:05
  • 2
    $\begingroup$ Watch this TED talk. But thinking that something is obvious doesn't prove anything and is of no use. $\endgroup$ – Pratik Deoghare Aug 16 '11 at 2:14
  • 6
    $\begingroup$ @MCH: Whether Feynman believed these things or not, I don't think he is a relevant example. First, both of those statements are widely believed to be true, and secondly he never claimed to have proved these things. $\endgroup$ – Joe Fitzsimons Aug 17 '11 at 13:14
  • 2
    $\begingroup$ True. Most of us think that, obviously, P $\neq$ NP. We just can't prove that! $\endgroup$ – Mahdi Cheraghchi Aug 17 '11 at 19:51
7
$\begingroup$

"I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug. Once I tell you what it is, you will understand why it escaped detection for two decades. Lest you think I'm picking on Bentley, let me tell you how I discovered the bug: The version of binary search that I wrote for the JDK contained the same bug. It was reported to Sun recently when it broke someone's program, after lying in wait for nine years or so."

--

Joshua Bloch "Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken" 2006

Improve this answer
$\endgroup$
1
  • 7
    $\begingroup$ This one isn't actually a bug in the algorithm, but a bug in the implementation. The algorithm is correct; the problem is that the "int" type can't actually deal with arbitrary integers. $\endgroup$ – Aaron Roth Aug 21 '11 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.