Errores importantes en los documentos FOCS / STOC aceptados [cerrado]
23
¿Te has encontrado con una ocasión como esa en el pasado? Bueno, hay una posibilidad para todo, pero me gustaría saber qué tan realista puede ser esta incidencia. Me refiero a errores graves que alteran el objetivo del trabajo y no a errores menores, por supuesto. Gracias
No quería hacer un gran problema. Si Lance lo publica, está bien :)
Suresh Venkat
55
@ N27: "La pregunta no pide una lista de documentos" sí, pero tener una lista grande de tales errores es mucho más útil. De lo contrario, el comentario de Suresh es el final de la historia, ya que responde afirmativamente a la pregunta. También sugiero cambiar FOCS / STOC para permitir otras conferencias "prestigiosas", e incluso revistas.
MS Dousti
66
Estoy un poco sorprendido de que esta pregunta aún no se haya cerrado. Todos los ejemplos de tales errores pueden ser vergonzosos, y podríamos ofender a los autores al repetir sus viejos errores. Debemos ser educados y profesionales, y esta pregunta es una solicitud de insultos. Estoy votando para cerrar esto ("fuera de tema" solo por la falta de una mejor razón).
Jukka Suomela
44
Estoy de acuerdo con Jukka en este caso. Voto virtual para cerrar.
Dave Clarke
Respuestas:
10
Un caso es el artículo STOC '88 de Blum-Feldman-Micali . El defecto les fue señalado por Mihir Bellare (comunicación privada). Puede encontrar la discusión relevante aquí .
El problema de accesibilidad a la red de Petri tiene una rica historia donde las pruebas incompletas o defectuosas luego conducen a nuevos resultados. GS Sacerdote y RL Tenney presentaron una prueba de decidabilidad incompleta en STOC '77 , que sin embargo fue instrumental en la prueba posterior de EW Mayr en STOC '81 y su mejora por SR Kosaraju en STOC '82 . Estas pruebas de capacidad de decisión no venían con límites superiores de complejidad (emplean cuasi ordenamientos para la terminación). Z. Bouziane más tarde afirmó haber encontrado un algoritmo 2ExpSpace en FOCS '98 . P. Jančar señaló una falla (y finalmente se publicó en una nota), pero el trabajo de Bouziane ha ayudado a renovar el interés en esta vieja pregunta. Aunque todavía no se conocen límites superiores sobre la complejidad de este problema, J. Leroux ha presentado recientemente una nueva prueba de capacidad de decisión en POPL '11 .
No en STOC / FOCS:
Otro caso ocurrió en la conferencia Estructura en teoría de la complejidad (1988) (si no me equivoco, ahora se llama Conferencia sobre la complejidad computacional). El título del artículo fue Sobre el poder de los protocolos interactivos de múltiples poderes . Dos años después, los autores (Fortnow, Rompel y Sipser) publicaron un documento de dos páginas "Errata for On the Power of Multi-Prover Interactive Protocols" en la misma conferencia. Desafortunadamente, IEEE no ofrece este documento para descargar.
@Andras: Sí. Además, la tesis de Fortnow cubre esto. @ Jukka: Mi respuesta original fue editada más tarde. No puedo comentar sobre la respuesta editada, pero en la parte de la respuesta que escribí, su punto no se aplica. Esto se debe a que las personas que originalmente escribieron el documento (defectuoso), luego señalaron los defectos en su documento original y los corrigieron. Por lo tanto, no hay problema en mencionarlos aquí.
MS Dousti
1
@Sadeq: ¿Cree que si las personas ya han pasado por la vergüenza de publicar un resultado defectuoso y luego publican una corrección a su error, estarán felices de ver que este viejo incidente se vuelve a publicar y publicitar aquí una vez más? ¿No ves alguna razón para ser un poco más cuidadoso y considerado aquí? Por supuesto, está perfectamente bien mencionar educadamente el error si alguien tiene una pregunta técnica relacionada con un problema en particular, pero en esta pregunta el único objetivo parece ser reunir algún tipo de salón de la vergüenza, sin ninguna buena razón, solo para satisfacer la curiosidad
Jukka Suomela
2
Pero entonces toda esta pregunta no debería hacerse, ¿verdad? quizás tiempo para una meta discusión.
Suresh Venkat
2
@Jukka: he editado mi edición para enfatizar mejor que estos resultados defectuosos tuvieron efectos muy positivos. Si crees que esto sigue siendo ofensivo, no me importa eliminar mis ediciones.
Sylvain
2
@Suresh: Sí, creo que la pregunta no debería haberse hecho; Ya comenté la pregunta y voté para cerrar.
Respuestas:
Un caso es el artículo STOC '88 de Blum-Feldman-Micali . El defecto les fue señalado por Mihir Bellare (comunicación privada). Puede encontrar la discusión relevante aquí .
El problema de accesibilidad a la red de Petri tiene una rica historia donde las pruebas incompletas o defectuosas luego conducen a nuevos resultados. GS Sacerdote y RL Tenney presentaron una prueba de decidabilidad incompleta en STOC '77 , que sin embargo fue instrumental en la prueba posterior de EW Mayr en STOC '81 y su mejora por SR Kosaraju en STOC '82 . Estas pruebas de capacidad de decisión no venían con límites superiores de complejidad (emplean cuasi ordenamientos para la terminación). Z. Bouziane más tarde afirmó haber encontrado un algoritmo 2ExpSpace en FOCS '98 . P. Jančar señaló una falla (y finalmente se publicó en una nota), pero el trabajo de Bouziane ha ayudado a renovar el interés en esta vieja pregunta. Aunque todavía no se conocen límites superiores sobre la complejidad de este problema, J. Leroux ha presentado recientemente una nueva prueba de capacidad de decisión en POPL '11 .
No en STOC / FOCS:
Otro caso ocurrió en la conferencia Estructura en teoría de la complejidad (1988) (si no me equivoco, ahora se llama Conferencia sobre la complejidad computacional). El título del artículo fue Sobre el poder de los protocolos interactivos de múltiples poderes . Dos años después, los autores (Fortnow, Rompel y Sipser) publicaron un documento de dos páginas "Errata for On the Power of Multi-Prover Interactive Protocols" en la misma conferencia. Desafortunadamente, IEEE no ofrece este documento para descargar.
fuente