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
$\begingroup$
$\endgroup$
14
-
5$\begingroup$ Yes. As Lance mentions, blog.computationalcomplexity.org/2011/03/stoc-1989.html $\endgroup$– Suresh VenkatCommented Apr 26, 2011 at 4:24
-
5$\begingroup$ @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. $\endgroup$– Sadeq DoustiCommented Apr 26, 2011 at 6:27
-
6$\begingroup$ 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). $\endgroup$– Jukka SuomelaCommented Apr 27, 2011 at 0:32
-
5$\begingroup$ 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. $\endgroup$– Radu GRIGoreCommented Apr 27, 2011 at 12:13
-
6$\begingroup$ 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. $\endgroup$– Peter ShorCommented Apr 27, 2011 at 19:05
|
Show 9 more comments
1 Answer
$\begingroup$
$\endgroup$
10
One case is Blum-Feldman-Micali's STOC '88 paper. The flaw was pointed to them by Mihir Bellare (private communication). You can find the relevant discussion here.
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, which was however instrumental in the later proof of E.W. Mayr at STOC '81 and its improvement by S.R. Kosaraju at STOC '82. These decidability proofs did not come with complexity upper bounds (they employ well quasi-orderings for termination). Z. Bouziane later claimed to have found a 2ExpSpace algorithm at FOCS '98. A flaw was pointed by P. Jančar (and finally published in a note), 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.
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. 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.
-
2$\begingroup$ @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. $\endgroup$ Commented Apr 27, 2011 at 2:00
-
1$\begingroup$ @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. $\endgroup$ Commented Apr 27, 2011 at 2:52
-
2$\begingroup$ But then this entire question shouldn't be asked, right ? maybe time for a meta discussion. $\endgroup$ Commented Apr 27, 2011 at 4:09
-
2$\begingroup$ @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. $\endgroup$– SylvainCommented Apr 27, 2011 at 9:06
-
2$\begingroup$ @Suresh: Yes, I think the question shouldn't have been asked; I already commented the question and voted to close. $\endgroup$ Commented Apr 27, 2011 at 11:22