<ul>
<li><p>One case is Blum-Feldman-Micali's <a href="http://portal.acm.org/citation.cfm?id=62222" rel="nofollow noreferrer">STOC '88 paper</a>. The flaw was pointed to them by Mihir Bellare (private communication). You can find the relevant discussion <a href="https://cstheory.stackexchange.com/q/2121/873">here</a>.</p></li>
<li><p>The <em>Petri net reachability</em> problem has a rich history where incomplete or flawed proofs later lead to new results.  G.S. Sacerdote and R.L. Tenney presented an incomplete decidability proof at <a href="http://dx.doi.org/10.1145/800105.803396Z" rel="nofollow noreferrer">STOC '77</a>, which was however instrumental in the later proof of E.W. Mayr at <a href="http://dx.doi.org/10.1145/800076.802477" rel="nofollow noreferrer">STOC '81</a> and its improvement by S.R. Kosaraju at <a href="http://dx.doi.org/10.1145/800070.802201" rel="nofollow noreferrer">STOC '82</a>.  These decidability proofs did not come with complexity upper bounds (they employ <a href="http://en.wikipedia.org/wiki/Well-quasi-ordering" rel="nofollow noreferrer">well quasi-orderings</a> for termination).  Z. Bouziane later claimed to have found a 2ExpSpace algorithm at <a href="http://dx.doi.org/10.1109/SFCS.1998.743436" rel="nofollow noreferrer">FOCS '98</a>.  A flaw was pointed by P. Jančar (and finally published in a <a href="http://dx.doi.org/10.1016/j.ic.2008.06.003" rel="nofollow noreferrer">note</a>), but Bouziane's work has helped renewing the interest into this old question.  Although there are still no known upper bounds on the complexity of this problem, J. Leroux has recently presented a new decidability proof at <a href="http://dx.doi.org/10.1145/1926385.1926421" rel="nofollow noreferrer">POPL '11</a>.</p></li>
</ul>

<p><strong>Not in STOC/FOCS:</strong></p>

<hr>

<p>Another case happened in Structure in Complexity Theory (1988) conference (If I'm not mistaken, it's now called Conference on Computational Complexity.) The paper's title was <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5275" rel="nofollow noreferrer">On the power of multi-power interactive protocols</a>. Two years later, the authors (Fortnow, Rompel, and Sipser) published a two-page paper "Errata for On the Power of Multi-Prover Interactive Protocols" in the same conference. Unfortunately, IEEE does not offer this paper for download.</p>

CC BY-SA 3.0
2011-04-26T21:49:06.087Z
At least there was a later journal version of the Fortnow, Rompel, Sipser paper http://dx.doi.org/10.1016/0304-3975(94)90251-8
András Salamon
CC BY-SA 3.0
2011-04-27T00:35:18.817Z
I flagged this answer for moderator attention, as it explicitly mentions some names of people and points out their (really old) mistakes. I don't see any need to do that, and it may hurt someone's feelings.
Jukka Suomela
CC BY-SA 3.0
2011-04-27T02:00:19.810Z
@Andras: Yes. Moreover, Fortnow's thesis covers this. @Jukka: My original answer was later edited. I can't comment on the edited answer, but in the part of the answer I wrote, your point does not apply. This is because the people who originally wrote the (flawed) paper, have later pointed out to the flaws in their original paper, and corrected them. There's therefore no problem mentioning them here.
Sadeq Dousti
CC BY-SA 3.0
2011-04-27T02:52:26.240Z
@Sadeq: Do you think that if people have already gone through the embarrassment of publishing a flawed result, and then publishing a correction to their mistake, they will be happy to see this old incident rehashed and publicised here once again? Don't you see any reason to be a bit more careful and considerate here? Of course it is perfectly fine to politely mention the mistake if someone has a *technical* question related to a particular problem, but in this question the only goal seems to be to put together some kind of hall of shame, for no good reason, just to satisfy the curiosity.
Jukka Suomela
CC BY-SA 3.0
2011-04-27T04:09:57.563Z
But then this entire question shouldn't be asked, right ? maybe time for a meta discussion.
Suresh Venkat
CC BY-SA 3.0
2011-04-27T04:49:11.100Z
@Jukka: AFAIK, both of the results in Blum-Feldman-Micali and Fortnow-Rompel-Sipser were correct; only their proofs were flawed. The flaw was later remedied by both teams, and technically they did great in proving the theorems. If I were them, I'd never be embarrassed; rather, I'd be honored to be able to fix the flaw. So, according to "do unto others as you would have others do unto you," I don't see a problem with mentioning them. However, this is a personal view, and as @Suresh said, I'd like to see others' judgement as well (in meta).
Sadeq Dousti
CC BY-SA 3.0
2011-04-27T09:06:54.747Z
@Jukka: I've edited my edit to better emphasize that these flawed results had very positive effects.  If you think this is still offensive I don't mind removing my edits.
Sylvain
CC BY-SA 3.0
2011-04-27T10:10:22.637Z
@Sylvain: At least **I** didn't think your part of answer was offensive. However, since I was not in the context, I just defended mine.
Sadeq Dousti
CC BY-SA 3.0
2011-04-27T11:22:56.037Z
@Suresh: Yes, I think the question shouldn't have been asked; I already commented the question and voted to close.
Jukka Suomela
CC BY-SA 3.0
2011-04-27T11:26:16.567Z
It seems that this question caused much trouble and this was not my intention. So, if you think that by closing it, will make things better, go ahead. I have no problem with that.
N27
CC BY-SA 3.0
2011-04-26T06:40:09.047Z
2011-04-27T09:05:34.937Z
2017-04-13T12:32:28.167Z
Sadeq Dousti
<p>Have you come across an occasion like that in the past? Well, there is a possibility for everything but I would like to know how realistic this incidence can be. I am referring to serious mistakes altering the target of the paper and not minor mistakes, of course. Thanks</p>

CC BY-SA 3.0
2011-04-26T04:24:24.843Z
Yes. As Lance mentions, http://blog.computationalcomplexity.org/2011/03/stoc-1989.html
Suresh Venkat
CC BY-SA 3.0
2011-04-26T05:18:37.970Z
@Suresh, why not posting it as an answer? (ps: the question seems to be implicitly asking for known cases which makes it a list question, therefore I made it CW. I also feel uneasy about the question for some reason but don't have a good argument for closing it.)
Kaveh
CC BY-SA 3.0
2011-04-26T05:19:30.927Z
I didn't want to make a big deal. If Lance posts it, that's fine :)
Suresh Venkat
CC BY-SA 3.0
2011-04-26T05:32:09.607Z
The question does not ask for a list of papers and this is quite obvious I think. Just for the possibility this may happen.
N27
CC BY-SA 3.0
2011-04-26T06:27:29.573Z
@N27: "The question does not ask for a list of papers" yes, but having a big-list of such mistakes is much more useful. Otherwise, Suresh's comment is the end of story, since it answers the question in the affirmative. I also suggest changing FOCS/STOC to allow other "prestigious" conferences, and even journals.
Sadeq Dousti
CC BY-SA 3.0
2011-04-26T06:40:38.400Z
@N27, let me quote: "there is a possibility for everything but I would like to know how realistic this incidence can be" so can you say what is your question? "**Have you come across an occasion like that in the past?**" Aren't you asking for real examples of this in the past? (I didn't mean that you are asking for a *list* as an answer, but that the answers will create a list of such examples.)
Kaveh
CC BY-SA 3.0
2011-04-26T06:47:27.153Z
I was looking for an answer like: "this has never happened as far as I know", or "there have been a couple of papers with serious mistakes over the last 5 years" etc. Of course, I have no problem with posting specific papers, but I did not ask for that too.
N27
CC BY-SA 3.0
2011-04-26T06:54:14.263Z
Maybe you haven't asked for specific papers explicitly, but the answers would probably state them in any case. (The first possible answer is false as Suresh's comment shows, the second one without mentioning papers would be quite subjective and argumentative. In any case, I still don't have good feelings about this question. I think this can turn into a discussion with/without mentioning the papers explicitly, which is not good. But I leave it to others to decide about it.)
Kaveh
CC BY-SA 3.0
2011-04-26T07:38:47.950Z
ps: in any case, apologies if I misunderstood your question, will be more careful next time.
Kaveh
CC BY-SA 3.0
2011-04-26T12:52:33.563Z
There may also have been papers withdrawn from FOCS and STOC before publication because of mistakes ... I vaguely remember hearing about one such case, but I may be confusing it with something else.
Peter Shor 
CC BY-SA 3.0
2011-04-27T00:32:32.123Z
I am a bit surprised that this question was not closed already. All examples of such mistakes may be embarrassing, and we might offend the authors by rehashing their old mistakes. We should be polite and professional, and this question is a request for insults. I am voting to close this ("off topic" just for the lack of a better reason).
Jukka Suomela
CC BY-SA 3.0
2011-04-27T07:02:47.053Z
I agree with Jukka on this one. Virtual vote to close.
Dave Clarke
CC BY-SA 3.0
2011-04-27T12:13:00.347Z
Perhaps the question could be rephrased as "What errata for FOCS/STOC papers are there?" The answer(s) (either a link to an existing list of errata or a list of links to errata) should be useful and not terribly embarrassing for authors, since it is they who point out the mistake.
Radu GRIGore
CC BY-SA 3.0
2011-04-27T19:05:54.980Z
I actually think it's a good idea to communicate the notion to students (and others who don't know) that FOCS/STOC papers can be wrong. On the other hand, we've done that effectively now and I don't *think* we've offended anybody so far, so we can close the question. I do have a FOCS/STOC paper with an incorrect proof of a correct result, which I have never actually published an erratum for. If the question is rephrased so that this is a valid answer, I'd be happy to answer it.
Peter Shor 
<soft-question><big-list><paper-review>
Major mistakes in accepted FOCS/STOC papers
N27
# Major mistakes in accepted FOCS/STOC papers

(Asked by: username_0 on 2011-04-26)

Have you come across an occasion like that in the past? Well, there is a possibility for everything but I would like to know how realistic this incidence can be. I am referring to serious mistakes altering the target of the paper and not minor mistakes, of course. Thanks

**Tags:** soft-question, big-list, paper-review
> **Comments:**
> **username_1**: Yes. As Lance mentions, http://blog.computationalcomplexity.org/2011/03/stoc-1989.html  
> **username_2**: @Suresh, why not posting it as an answer? (ps: the question seems to be implicitly asking for known cases which makes it a list question, therefore I made it CW. I also feel uneasy about the question for some reason but don't have a good argument for closing it.)  
> **username_1**: I didn't want to make a big deal. If Lance posts it, that's fine :)  
> **username_0**: The question does not ask for a list of papers and this is quite obvious I think. Just for the possibility this may happen.  
> **username_3**: @N27: "The question does not ask for a list of papers" yes, but having a big-list of such mistakes is much more useful. Otherwise, Suresh's comment is the end of story, since it answers the question in the affirmative. I also suggest changing FOCS/STOC to allow other "prestigious" conferences, and even journals.  
> **username_2**: @N27, let me quote: "there is a possibility for everything but I would like to know how realistic this incidence can be" so can you say what is your question? "**Have you come across an occasion like that in the past?**" Aren't you asking for real examples of this in the past? (I didn't mean that you are asking for a *list* as an answer, but that the answers will create a list of such examples.)  
> **username_0**: I was looking for an answer like: "this has never happened as far as I know", or "there have been a couple of papers with serious mistakes over the last 5 years" etc. Of course, I have no problem with posting specific papers, but I did not ask for that too.  
> **username_2**: Maybe you haven't asked for specific papers explicitly, but the answers would probably state them in any case. (The first possible answer is false as Suresh's comment shows, the second one without mentioning papers would be quite subjective and argumentative. In any case, I still don't have good feelings about this question. I think this can turn into a discussion with/without mentioning the papers explicitly, which is not good. But I leave it to others to decide about it.)  
> **username_2**: ps: in any case, apologies if I misunderstood your question, will be more careful next time.  
> **username_4**: There may also have been papers withdrawn from FOCS and STOC before publication because of mistakes ... I vaguely remember hearing about one such case, but I may be confusing it with something else.  
> **username_5**: I am a bit surprised that this question was not closed already. All examples of such mistakes may be embarrassing, and we might offend the authors by rehashing their old mistakes. We should be polite and professional, and this question is a request for insults. I am voting to close this ("off topic" just for the lack of a better reason).  
> **username_6**: I agree with Jukka on this one. Virtual vote to close.  
> **username_7**: Perhaps the question could be rephrased as "What errata for FOCS/STOC papers are there?" The answer(s) (either a link to an existing list of errata or a list of links to errata) should be useful and not terribly embarrassing for authors, since it is they who point out the mistake.  
> **username_4**: I actually think it's a good idea to communicate the notion to students (and others who don't know) that FOCS/STOC papers can be wrong. On the other hand, we've done that effectively now and I don't *think* we've offended anybody so far, so we can close the question. I do have a FOCS/STOC paper with an incorrect proof of a correct result, which I have never actually published an erratum for. If the question is rephrased so that this is a valid answer, I'd be happy to answer it.  

---

## 1 answers

### Answer by username_3 on 2011-04-26. Score: 11 | Accepted answer

* One case is Blum-Feldman-Micali's [STOC '88 paper](http://portal.acm.org/citation.cfm?id=62222). The flaw was pointed to them by Mihir Bellare (private communication). You can find the relevant discussion [here](https://cstheory.stackexchange.com/q/2121/873).
* The *Petri net reachability* problem has a rich history where incomplete or flawed proofs later lead to new results. G.S. Sacerdote and R.L. Tenney presented an incomplete decidability proof at [STOC '77](http://dx.doi.org/10.1145/800105.803396Z), which was however instrumental in the later proof of E.W. Mayr at [STOC '81](http://dx.doi.org/10.1145/800076.802477) and its improvement by S.R. Kosaraju at [STOC '82](http://dx.doi.org/10.1145/800070.802201). These decidability proofs did not come with complexity upper bounds (they employ [well quasi-orderings](http://en.wikipedia.org/wiki/Well-quasi-ordering) for termination). Z. Bouziane later claimed to have found a 2ExpSpace algorithm at [FOCS '98](http://dx.doi.org/10.1109/SFCS.1998.743436). A flaw was pointed by P. Jančar (and finally published in a [note](http://dx.doi.org/10.1016/j.ic.2008.06.003)), but Bouziane's work has helped renewing the interest into this old question. Although there are still no known upper bounds on the complexity of this problem, J. Leroux has recently presented a new decidability proof at [POPL '11](http://dx.doi.org/10.1145/1926385.1926421).

**Not in STOC/FOCS:**

---

Another case happened in Structure in Complexity Theory (1988) conference (If I'm not mistaken, it's now called Conference on Computational Complexity.) The paper's title was [On the power of multi-power interactive protocols](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5275). Two years later, the authors (Fortnow, Rompel, and Sipser) published a two-page paper "Errata for On the Power of Multi-Prover Interactive Protocols" in the same conference. Unfortunately, IEEE does not offer this paper for download.

> **Comments:**
> **username_8**: At least there was a later journal version of the Fortnow, Rompel, Sipser paper http://dx.doi.org/10.1016/0304-3975(94)90251-8  
> **username_5**: I flagged this answer for moderator attention, as it explicitly mentions some names of people and points out their (really old) mistakes. I don't see any need to do that, and it may hurt someone's feelings.  
> **username_3**: @Andras: Yes. Moreover, Fortnow's thesis covers this. @Jukka: My original answer was later edited. I can't comment on the edited answer, but in the part of the answer I wrote, your point does not apply. This is because the people who originally wrote the (flawed) paper, have later pointed out to the flaws in their original paper, and corrected them. There's therefore no problem mentioning them here.  
> **username_5**: @Sadeq: Do you think that if people have already gone through the embarrassment of publishing a flawed result, and then publishing a correction to their mistake, they will be happy to see this old incident rehashed and publicised here once again? Don't you see any reason to be a bit more careful and considerate here? Of course it is perfectly fine to politely mention the mistake if someone has a *technical* question related to a particular problem, but in this question the only goal seems to be to put together some kind of hall of shame, for no good reason, just to satisfy the curiosity.  
> **username_1**: But then this entire question shouldn't be asked, right ? maybe time for a meta discussion.  
> **username_3**: @Jukka: AFAIK, both of the results in Blum-Feldman-Micali and Fortnow-Rompel-Sipser were correct; only their proofs were flawed. The flaw was later remedied by both teams, and technically they did great in proving the theorems. If I were them, I'd never be embarrassed; rather, I'd be honored to be able to fix the flaw. So, according to "do unto others as you would have others do unto you," I don't see a problem with mentioning them. However, this is a personal view, and as @Suresh said, I'd like to see others' judgement as well (in meta).  
> **username_9**: @Jukka: I've edited my edit to better emphasize that these flawed results had very positive effects.  If you think this is still offensive I don't mind removing my edits.  
> **username_3**: @Sylvain: At least **I** didn't think your part of answer was offensive. However, since I was not in the context, I just defended mine.  
> **username_5**: @Suresh: Yes, I think the question shouldn't have been asked; I already commented the question and voted to close.  
> **username_0**: It seems that this question caused much trouble and this was not my intention. So, if you think that by closing it, will make things better, go ahead. I have no problem with that.  

---

