27

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

Jacob
  • 153
  • 5
shabunc
  • 121
  • 1
  • 6
  • 13
    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. – Jagadish Aug 15 '11 at 17:24
  • @Jagadish - no, actually wonderful example, thank you! It is a pity it is not an answer to up vote it. – shabunc Aug 15 '11 at 18:11
  • 2
    @shabunc these kinds of questions are asking for a list of answers, and so the community-wiki tag is appropriate for it. – Suresh Venkat Aug 15 '11 at 18:47
  • 4
    also, this question is related: http://cstheory.stackexchange.com/questions/3616/common-false-beliefs-in-theoretical-computer-science – Suresh Venkat Aug 15 '11 at 18:48
  • @Suresh, I've added the appropriate tag, thank you. As for related question - actually, it is quite different. Mine is about mistakes which nobody recognize for some lengthy period, that one about common misconceptions (which nevertheless are not recognized as correct) – shabunc Aug 15 '11 at 18:53
  • 1
    I think that the word “confusions” in the title is too vague and should be replaced by “errors” or other specific words. – Tsuyoshi Ito Aug 16 '11 at 14:32
  • 1
    @Tsuyoshi - well, I've tried to be polite and not to harm anybody, but you are right, let it be "error" – shabunc Aug 16 '11 at 14:37
  • 2
    If asking about errors is impolite, your question itself is impolite and avoiding the word “errors” in the title is not a solution. – Tsuyoshi Ito Aug 16 '11 at 14:40
  • 3
    Relevant blog post Math Is Like The Stock Market. – Pratik Deoghare Aug 18 '11 at 18:17
  • Maybe the question should be edited in such a way that the answers will be focused on TCS and not CS in general, as in the case of David Cary's answer below. – Alessandro Cosentino Aug 22 '11 at 02:51

5 Answers5

28

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

Jeffε
  • 23,129
  • 10
  • 96
  • 163
  • @JɛffE, this one is great example, thank you! – shabunc Aug 18 '11 at 13:42
  • 4
    Do you happen to know who the clever student was ? – Suresh Venkat Aug 19 '11 at 00:08
  • 4
    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. – Jeffε Aug 19 '11 at 06:23
10

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.

Loïck
  • 233
  • 1
  • 7
  • 8
    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. – Mahdi Cheraghchi Aug 16 '11 at 18:34
  • 1
    agree with MCH, crypto protocols are subtle different story. – shabunc Aug 16 '11 at 18:37
  • 6
    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. – Loïck Aug 18 '11 at 15:35
9

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.

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
8

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.

Mahdi Cheraghchi
  • 4,031
  • 22
  • 30
7

"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

Jukka Suomela
  • 11,500
  • 2
  • 53
  • 116
David Cary
  • 532
  • 3
  • 11
  • 7
    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. – Aaron Roth Aug 21 '11 at 13:20