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
closed as not constructive by Jukka Suomela, Suresh Venkat Apr 27 '11 at 16:39
As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. If this question can be reworded to fit the rules in the help center, please edit the question.
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.