Schwerwiegende Fehler in akzeptierten FOCS / STOC-Papieren [geschlossen]
23
Haben Sie in der Vergangenheit einen solchen Anlass erlebt? Nun, es gibt für alles eine Möglichkeit, aber ich würde gerne wissen, wie realistisch dieses Ereignis sein kann. Ich beziehe mich auf schwerwiegende Fehler, die das Ziel der Veröffentlichung verändern, und natürlich nicht auf geringfügige Fehler. Vielen Dank
Ich wollte keine große Sache machen. Wenn Lance es postet, ist das in Ordnung :)
Suresh Venkat
5
@ N27: "Die Frage fragt nicht nach einer Liste von Artikeln" ja, aber eine große Liste solcher Fehler ist viel nützlicher. Ansonsten ist Sureshs Kommentar das Ende der Geschichte, da er die Frage bejaht. Ich schlage auch vor, FOCS / STOC zu ändern, um andere "angesehene" Konferenzen und sogar Zeitschriften zuzulassen.
MS Dousti
6
Ich bin ein bisschen überrascht, dass diese Frage nicht bereits geschlossen wurde. Alle Beispiele für solche Fehler mögen peinlich sein, und wir könnten die Autoren beleidigen, indem wir ihre alten Fehler aufarbeiten. Wir sollten höflich und professionell sein und diese Frage ist eine Bitte um Beleidigung. Ich stimme dafür, dies zu schließen ("off topic", nur aus Mangel an einem besseren Grund).
Jukka Suomela
4
Da stimme ich Jukka zu. Virtuelle Abstimmung zum Schließen.
Dave Clarke
Antworten:
10
Ein Fall ist das STOC '88-Papier von Blum-Feldman-Micali . Auf den Mangel wurde von Mihir Bellare (private Mitteilung) hingewiesen. Die entsprechende Diskussion finden Sie hier .
Das Problem der Erreichbarkeit von Petri-Netzen hat eine lange Geschichte, in der unvollständige oder fehlerhafte Beweise später zu neuen Ergebnissen führen. GS Sacerdote und RL Tenney legten auf der STOC '77 einen unvollständigen Entscheidbarkeitsnachweis vor , der jedoch maßgeblich zum späteren Nachweis von EW Mayr auf der STOC '81 und seiner Verbesserung durch SR Kosaraju auf der STOC '82 beitrug . Diese Entscheidbarkeitsnachweise enthielten keine Obergrenzen für die Komplexität (sie verwenden quasi gute Ordnungen für die Beendigung). Z. Bouziane behauptete später, am FOCS '98 einen 2ExpSpace-Algorithmus gefunden zu haben . Auf einen Fehler wurde von P. Jančar hingewiesen (und schließlich in einer Notiz veröffentlicht)), aber Bouzianes Arbeit hat dazu beigetragen, das Interesse an dieser alten Frage zu erneuern. Obwohl es immer noch keine bekannten Obergrenzen für die Komplexität dieses Problems gibt, hat J. Leroux kürzlich auf der POPL '11 einen neuen Entscheidbarkeitsbeweis vorgelegt .
Nicht in STOC / FOCS:
Ein weiterer Fall ereignete sich in der Konferenz Structure in Complexity Theory (1988) (Wenn ich mich nicht irre, heißt sie jetzt Conference on Computational Complexity.) Der Titel des Papiers lautete: On the power of multi-power interactive protocols . Zwei Jahre später veröffentlichten die Autoren (Fortnow, Rompel und Sipser) in derselben Konferenz ein zweiseitiges Papier "Errata for On the Power von interaktiven Multi-Prover-Protokollen". Leider bietet IEEE dieses Papier nicht zum Download an.
@Andras: Ja. Darüber hinaus befasst sich Fortnows These. @Jukka: Meine ursprüngliche Antwort wurde später bearbeitet. Ich kann die bearbeitete Antwort nicht kommentieren, aber in dem Teil der Antwort, den ich geschrieben habe, trifft Ihr Punkt nicht zu. Dies liegt daran, dass die Leute, die ursprünglich das (fehlerhafte) Papier geschrieben haben, später auf die Fehler in ihrem Originalpapier hingewiesen und sie korrigiert haben. Es ist daher kein Problem, sie hier zu erwähnen.
MS Dousti
1
@Sadeq: Denken Sie, dass die Leute, die es schon peinlich fanden, ein fehlerhaftes Ergebnis zu veröffentlichen und dann eine Korrektur für ihren Fehler zu veröffentlichen, froh sind, wenn dieser alte Vorfall hier noch einmal aufgearbeitet und veröffentlicht wird? Sehen Sie keinen Grund, hier etwas vorsichtiger und rücksichtsvoller zu sein? Natürlich ist es völlig in Ordnung, den Fehler höflich zu erwähnen, wenn jemand eine technische Frage zu einem bestimmten Problem hat, aber in dieser Frage scheint das einzige Ziel darin zu bestehen, eine Art Hall of Shame zusammenzustellen, ohne guten Grund, nur um befriedige die Neugier.
Jukka Suomela
2
Aber dann sollte diese ganze Frage nicht gestellt werden, oder? vielleicht zeit für eine metadiskussion.
Suresh Venkat
2
@Jukka: Ich habe meine Bearbeitung bearbeitet, um besser hervorzuheben, dass diese fehlerhaften Ergebnisse sehr positive Auswirkungen hatten. Wenn du denkst, dass dies immer noch anstößig ist, habe ich nichts dagegen, meine Änderungen zu entfernen.
Sylvain
2
@ Suresh: Ja, ich denke, die Frage hätte nicht gestellt werden dürfen. Ich habe die Frage bereits kommentiert und zum Schließen gestimmt.
Antworten:
Ein Fall ist das STOC '88-Papier von Blum-Feldman-Micali . Auf den Mangel wurde von Mihir Bellare (private Mitteilung) hingewiesen. Die entsprechende Diskussion finden Sie hier .
Das Problem der Erreichbarkeit von Petri-Netzen hat eine lange Geschichte, in der unvollständige oder fehlerhafte Beweise später zu neuen Ergebnissen führen. GS Sacerdote und RL Tenney legten auf der STOC '77 einen unvollständigen Entscheidbarkeitsnachweis vor , der jedoch maßgeblich zum späteren Nachweis von EW Mayr auf der STOC '81 und seiner Verbesserung durch SR Kosaraju auf der STOC '82 beitrug . Diese Entscheidbarkeitsnachweise enthielten keine Obergrenzen für die Komplexität (sie verwenden quasi gute Ordnungen für die Beendigung). Z. Bouziane behauptete später, am FOCS '98 einen 2ExpSpace-Algorithmus gefunden zu haben . Auf einen Fehler wurde von P. Jančar hingewiesen (und schließlich in einer Notiz veröffentlicht)), aber Bouzianes Arbeit hat dazu beigetragen, das Interesse an dieser alten Frage zu erneuern. Obwohl es immer noch keine bekannten Obergrenzen für die Komplexität dieses Problems gibt, hat J. Leroux kürzlich auf der POPL '11 einen neuen Entscheidbarkeitsbeweis vorgelegt .
Nicht in STOC / FOCS:
Ein weiterer Fall ereignete sich in der Konferenz Structure in Complexity Theory (1988) (Wenn ich mich nicht irre, heißt sie jetzt Conference on Computational Complexity.) Der Titel des Papiers lautete: On the power of multi-power interactive protocols . Zwei Jahre später veröffentlichten die Autoren (Fortnow, Rompel und Sipser) in derselben Konferenz ein zweiseitiges Papier "Errata for On the Power von interaktiven Multi-Prover-Protokollen". Leider bietet IEEE dieses Papier nicht zum Download an.
quelle