Erreurs majeures dans les documents FOCS / STOC acceptés [clôturé]
23
Avez-vous rencontré une telle occasion dans le passé? Eh bien, il y a une possibilité pour tout, mais j'aimerais savoir dans quelle mesure cette incidence peut être réaliste. Je fais référence à de graves erreurs modifiant l’objectif du document et non à des erreurs mineures, bien sûr. Merci
Je ne voulais pas faire une grosse affaire. Si Lance le poste, c'est bien :)
Suresh Venkat
5
@ N27: "La question ne demande pas de liste de papiers" oui, mais avoir une grande liste de ces erreurs est beaucoup plus utile. Sinon, le commentaire de Suresh est la fin de l'histoire, car il répond à la question par l'affirmative. Je suggère également de changer FOCS / STOC pour permettre d'autres conférences "prestigieuses", et même des revues.
MS Dousti
6
Je suis un peu surpris que cette question ne soit pas déjà close. Tous les exemples de telles erreurs peuvent être embarrassants et nous pouvons offenser les auteurs en ressassant leurs anciennes erreurs. Nous devons être polis et professionnels, et cette question est une demande d'insultes. Je vote pour clore ce sujet ("hors sujet" juste faute d'une meilleure raison).
Jukka Suomela
4
Je suis d'accord avec Jukka sur celui-ci. Vote virtuel pour clôturer.
Dave Clarke
Réponses:
10
Un cas est le papier STOC '88 de Blum-Feldman-Micali . La faille leur a été signalée par Mihir Bellare (communication privée). Vous pouvez trouver la discussion pertinente ici .
Le problème d' accessibilité nette de Petri a une histoire riche où des preuves incomplètes ou erronées conduisent plus tard à de nouveaux résultats. GS Sacerdote et RL Tenney ont présenté une preuve de décidabilité incomplète au STOC '77 , qui a cependant joué un rôle déterminant dans la preuve ultérieure d'EW Mayr au STOC '81 et de son amélioration par SR Kosaraju au STOC '82 . Ces preuves de décidabilité n'étaient pas accompagnées de limites supérieures de complexité (elles utilisent bien des quasi-ordonnances pour la terminaison). Z. Bouziane a affirmé plus tard avoir trouvé un algorithme 2ExpSpace à FOCS '98 . Une faille a été signalée par P. Jančar (et finalement publiée dans une note), mais le travail de Bouziane a permis de renouveler l'intérêt pour cette vieille question. Bien qu'il n'y ait toujours pas de limites supérieures connues sur la complexité de ce problème, J. Leroux a récemment présenté une nouvelle preuve de décidabilité au POPL '11 .
Pas dans STOC / FOCS:
Un autre cas s'est produit dans la conférence Structure in Complexity Theory (1988) (Si je ne me trompe pas, elle s'appelle désormais Conférence sur la complexité informatique.) Le titre de l'article était Sur la puissance des protocoles interactifs multi-puissance . Deux ans plus tard, les auteurs (Fortnow, Rompel et Sipser) ont publié un article de deux pages "Errata for On the Power of Multi-Prover Interactive Protocols" dans la même conférence. Malheureusement, l'IEEE ne propose pas ce document en téléchargement.
@Andras: Oui. De plus, la thèse de Fortnow couvre cela. @Jukka: Ma réponse originale a été modifiée ultérieurement. Je ne peux pas commenter la réponse modifiée, mais dans la partie de la réponse que j'ai écrite, votre point ne s'applique pas. Cela est dû au fait que les personnes qui ont écrit à l'origine le document (défectueux) ont par la suite signalé les défauts dans leur document d'origine et les ont corrigées. Il n'y a donc aucun problème à les mentionner ici.
MS Dousti
1
@Sadeq: Pensez-vous que si les gens ont déjà eu l'embarras de publier un résultat erroné, puis de publier une correction à leur erreur, ils seront heureux de voir ce vieil incident ressuscité et rendu public ici une fois de plus? Ne voyez-vous aucune raison d'être un peu plus prudent et attentionné ici? Bien sûr, il est parfaitement bien de mentionner poliment l'erreur si quelqu'un a une question technique liée à un problème particulier, mais dans cette question, le seul objectif semble être de mettre en place une sorte de salle de la honte, sans raison valable, juste pour satisfaire la curiosité.
Jukka Suomela
2
Mais alors toute cette question ne devrait pas être posée, non? peut-être le temps d'une méta discussion.
Suresh Venkat
2
@Jukka: J'ai modifié mon montage pour mieux souligner que ces résultats erronés ont eu des effets très positifs. Si vous pensez que cela est toujours offensant, cela ne me dérange pas de supprimer mes modifications.
Sylvain
2
@Suresh: Oui, je pense que la question n'aurait pas dû être posée; J'ai déjà commenté la question et voté pour la clôture.
Réponses:
Un cas est le papier STOC '88 de Blum-Feldman-Micali . La faille leur a été signalée par Mihir Bellare (communication privée). Vous pouvez trouver la discussion pertinente ici .
Le problème d' accessibilité nette de Petri a une histoire riche où des preuves incomplètes ou erronées conduisent plus tard à de nouveaux résultats. GS Sacerdote et RL Tenney ont présenté une preuve de décidabilité incomplète au STOC '77 , qui a cependant joué un rôle déterminant dans la preuve ultérieure d'EW Mayr au STOC '81 et de son amélioration par SR Kosaraju au STOC '82 . Ces preuves de décidabilité n'étaient pas accompagnées de limites supérieures de complexité (elles utilisent bien des quasi-ordonnances pour la terminaison). Z. Bouziane a affirmé plus tard avoir trouvé un algorithme 2ExpSpace à FOCS '98 . Une faille a été signalée par P. Jančar (et finalement publiée dans une note), mais le travail de Bouziane a permis de renouveler l'intérêt pour cette vieille question. Bien qu'il n'y ait toujours pas de limites supérieures connues sur la complexité de ce problème, J. Leroux a récemment présenté une nouvelle preuve de décidabilité au POPL '11 .
Pas dans STOC / FOCS:
Un autre cas s'est produit dans la conférence Structure in Complexity Theory (1988) (Si je ne me trompe pas, elle s'appelle désormais Conférence sur la complexité informatique.) Le titre de l'article était Sur la puissance des protocoles interactifs multi-puissance . Deux ans plus tard, les auteurs (Fortnow, Rompel et Sipser) ont publié un article de deux pages "Errata for On the Power of Multi-Prover Interactive Protocols" dans la même conférence. Malheureusement, l'IEEE ne propose pas ce document en téléchargement.
la source