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

CC BY-SA 3.0
2011-08-16T18:34:16.790Z
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
CC BY-SA 3.0
2011-08-16T18:37:52.667Z
agree with MCH, crypto protocols are subtle different story.
shabunc
CC BY-SA 3.0
2011-08-18T15:35:37.203Z
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
CC BY-SA 3.0
2011-08-16T17:14:00.400Z
2011-08-16T17:14:00.400Z
Loïck
<p><a href="http://rjlipton.wordpress.com/2011/08/18/math-is-like-the-stock-market/">Dick Lipton has a new post out</a> 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. </p>

CC BY-SA 3.0
2011-08-20T17:11:45.130Z
2011-08-20T17:11:45.130Z
Suresh Venkat
<p>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.</p>

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

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

CC BY-SA 3.0
2011-08-16T01:57:52.830Z
+1 for Feynman. Can you provide more details about Feynman and P vs NP?
a06e
CC BY-SA 3.0
2011-08-16T02:05:51.730Z
Ask Scott Aaronson, he knows this stuff well.
Mahdi Cheraghchi
CC BY-SA 3.0
2011-08-16T02:14:04.117Z
Watch [this TED talk](http://www.youtube.com/watch?v=SczraSQE3MY). But thinking that something is obvious doesn't prove anything and is of no use.
Pratik Deoghare
CC BY-SA 3.0
2011-08-17T13:14:07.777Z
@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.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-17T19:51:26.767Z
True. Most of us think that, _obviously_, P $\neq$ NP. We just can't prove that!
Mahdi Cheraghchi
CC BY-SA 3.0
2011-08-30T12:29:45.323Z
As Dick Lipton said in his blog, is quite embarassing that the majority of us believes that _"obviously"_ P $\neq$ NP without being able to even prove that SAT is not doable in linear time.
Giorgio Camerani
CC BY-SA 3.0
2011-08-16T00:16:22.987Z
2011-08-17T02:15:15.997Z
2011-08-17T02:15:15.997Z
Mahdi Cheraghchi
<p>"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."</p>

<p>--</p>

<p>Joshua Bloch
<a href="http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html">"Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken"</a>
2006</p>

CC BY-SA 3.0
2011-08-21T13:20:53.207Z
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
CC BY-SA 3.0
2011-08-21T03:23:09.320Z
2011-08-21T08:26:38.527Z
2011-08-21T08:26:38.527Z
David Cary
<p>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.</p>

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

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

<p>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 <em>huge</em> 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.) </p>

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

CC BY-SA 3.0
2011-08-18T13:42:05.563Z
@JɛﬀE, this one is great example, thank you!
shabunc
CC BY-SA 3.0
2011-08-19T00:08:06.310Z
Do you happen to know who the clever student was ?
Suresh Venkat
CC BY-SA 3.0
2011-08-19T06:23:57.927Z
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ε
CC BY-SA 3.0
2011-08-18T13:39:52.063Z
2011-08-18T13:39:52.063Z
Jeffε
<p>This is my first question on the cstheory stack, so don't be too rude if I'm violating etiquette somehow ) </p>

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

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

CC BY-SA 3.0
2011-08-15T17:24:36.707Z
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
CC BY-SA 3.0
2011-08-15T18:11:14.377Z
@Jagadish - no, actually wonderful example, thank you! It is a pity it is not an answer to up vote it.
shabunc
CC BY-SA 3.0
2011-08-15T18:47:30.730Z
@shabunc these kinds of questions are asking for a list of answers, and so the community-wiki tag is appropriate for it.
Suresh Venkat
CC BY-SA 3.0
2011-08-15T18:48:39.717Z
also, this question is related: http://cstheory.stackexchange.com/questions/3616/common-false-beliefs-in-theoretical-computer-science
Suresh Venkat
CC BY-SA 3.0
2011-08-15T18:53:01.073Z
@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
CC BY-SA 3.0
2011-08-16T14:32:17.587Z
I think that the word “confusions” in the title is too vague and should be replaced by “errors” or other specific words.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-16T14:37:43.323Z
@Tsuyoshi - well, I've tried to be polite and not to harm anybody, but you are right, let it be "error"
shabunc
CC BY-SA 3.0
2011-08-16T14:40:39.180Z
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
CC BY-SA 3.0
2011-08-18T18:17:29.257Z
Relevant blog post [Math Is Like The Stock Market](http://rjlipton.wordpress.com/2011/08/18/math-is-like-the-stock-market/).
Pratik Deoghare
CC BY-SA 3.0
2011-08-22T02:51:07.983Z
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
<soft-question><big-list>
Long-lasting errors in computer science
shabunc
# Long-lasting errors in computer science

(Asked by: username_0 on 2011-08-15)

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

**Tags:** soft-question, big-list

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 - no, actually wonderful example, thank you! It is a pity it is not an answer to up vote it.  
> **username_2**: @username_0 these kinds of questions are asking for a list of answers, and so the community-wiki tag is appropriate for it.  
> **username_2**: also, this question is related: http://cstheory.stackexchange.com/questions/3616/common-false-beliefs-in-theoretical-computer-science  
> **username_0**: @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)  
> **username_3**: I think that the word “confusions” in the title is too vague and should be replaced by “errors” or other specific words.  
> **username_0**: @Tsuyoshi - well, I've tried to be polite and not to harm anybody, but you are right, let it be "error"  
> **username_3**: If asking about errors is impolite, your question itself is impolite and avoiding the word “errors” in the title is not a solution.  
> **username_4**: Relevant blog post [Math Is Like The Stock Market](http://rjlipton.wordpress.com/2011/08/18/math-is-like-the-stock-market/).  
> **username_5**: 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 username_11's answer below.  

---

## 5 answers

### Answer by username_13 on 2011-08-18. Score: 29 | Accepted answer

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

> **Comments:**
> **username_0**: @JɛﬀE, this one is great example, thank you!  
> **username_2**: Do you happen to know who the clever student was ?  
> **username_13**: 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.  

---

### Answer by username_6 on 2011-08-16. Score: 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.

> **Comments:**
> **username_7**: 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.  
> **username_0**: agree with MCH, crypto protocols are subtle different story.  
> **username_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.  

---

### Answer by username_2 on 2011-08-20. Score: 9

[Dick Lipton has a new post out](http://rjlipton.wordpress.com/2011/08/18/math-is-like-the-stock-market/) 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.


---

### Answer by username_7 on 2011-08-16. Score: 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.

> **Comments:**
> **username_8**: +1 for Feynman. Can you provide more details about Feynman and P vs NP?  
> **username_7**: Ask Scott Aaronson, he knows this stuff well.  
> **username_4**: Watch [this TED talk](http://www.youtube.com/watch?v=SczraSQE3MY). But thinking that something is obvious doesn't prove anything and is of no use.  
> **username_9**: @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.  
> **username_7**: True. Most of us think that, _obviously_, P $\neq$ NP. We just can't prove that!  
> **username_10**: As Dick Lipton said in his blog, is quite embarassing that the majority of us believes that _"obviously"_ P $\neq$ NP without being able to even prove that SAT is not doable in linear time.  

---

### Answer by username_11 on 2011-08-21. Score: 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"](http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html)
2006

> **Comments:**
> **username_12**: 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.  

---

