Principais erros nos documentos aceitos do FOCS / STOC [fechado]
23
Você já se deparou com uma ocasião como essa no passado? Bem, há uma possibilidade para tudo, mas eu gostaria de saber o quão realista essa incidência pode ser. Refiro-me a erros graves que alteram o objetivo do trabalho e não a erros menores, é claro. obrigado
Eu não queria fazer um grande negócio. Se Lance mensagens, isso é bom :)
Suresh Venkat
5
@ N27: "A questão não pede uma lista de papéis" sim, mas ter uma grande lista desses erros é muito mais útil. Caso contrário, o comentário de Suresh é o fim da história, pois responde afirmativamente à pergunta. Sugiro também alterar o FOCS / STOC para permitir outras conferências "prestigiadas" e até periódicos.
MS Dousti
6
Estou um pouco surpreso que esta questão ainda não tenha sido encerrada. Todos os exemplos de tais erros podem ser embaraçosos, e podemos ofender os autores revisando seus erros antigos. Devemos ser educados e profissionais, e essa pergunta é uma solicitação de insultos. Estou votando para encerrar isso ("fora do tópico" apenas por falta de um motivo melhor).
Jukka Suomela
4
Eu concordo com Jukka neste. Votação virtual para fechar.
Dave Clarke
Respostas:
10
Um caso é o artigo STOC '88 de Blum-Feldman-Micali . A falha foi apontada por Mihir Bellare (comunicação privada). Você pode encontrar a discussão relevante aqui .
O problema de alcançabilidade da rede de Petri tem uma história rica, onde provas incompletas ou falhas levam a novos resultados. GS Sacerdote e RL Tenney apresentaram uma prova incompleta de decidibilidade no STOC '77 , o que foi fundamental para a prova posterior de EW Mayr no STOC '81 e sua melhoria por SR Kosaraju no STOC '82 . Essas provas de decidibilidade não vinham com limites superiores de complexidade (eles empregam quase pedidos ordenados para rescisão). Z. Bouziane mais tarde afirmou ter encontrado um algoritmo 2ExpSpace no FOCS '98 . Uma falha foi apontada por P. Jančar (e finalmente publicada em uma nota), mas o trabalho de Bouziane ajudou a renovar o interesse nessa antiga questão. Embora ainda não haja limites superiores conhecidos sobre a complexidade desse problema, J. Leroux apresentou recentemente uma nova prova de decidibilidade no POPL '11 .
Não em STOC / FOCS:
Outro caso aconteceu na conferência Structure in Complexity Theory (1988) (se não me engano, agora é chamada Conference on Computational Complexity.) O título do artigo era Sobre o poder de protocolos interativos de várias potências . Dois anos depois, os autores (Fortnow, Rompel e Sipser) publicaram um artigo de duas páginas "Erratas para o poder dos protocolos interativos de múltiplos provedores" na mesma conferência. Infelizmente, o IEEE não oferece este documento para download.
@ Andras: Sim. Além disso, a tese de Fortnow cobre isso. @Jukka: Minha resposta original foi editada mais tarde. Não posso comentar a resposta editada, mas na parte da resposta que escrevi, seu argumento não se aplica. Isso ocorre porque as pessoas que escreveram originalmente o artigo (defeituoso), mais tarde apontaram as falhas em seu artigo original e as corrigiram. Portanto, não há problema em mencioná-los aqui.
MS Dousti
1
@Sadeq: Você acha que se as pessoas já passaram pelo constrangimento de publicar um resultado defeituoso e depois publicarem uma correção por seu erro, ficarão felizes em ver esse velho incidente reformulado e divulgado aqui mais uma vez? Você não vê nenhuma razão para ser um pouco mais cuidadoso e atencioso aqui? É claro que é perfeitamente bom mencionar educadamente o erro se alguém tiver uma pergunta técnica relacionada a um problema específico, mas nessa pergunta o único objetivo parece ser reunir algum tipo de vergonha, sem uma boa razão, apenas para satisfazer a curiosidade.
Jukka Suomela
2
Mas então toda essa pergunta não deve ser feita, certo? talvez seja hora de uma meta discussão.
precisa saber é o seguinte
2
@Jukka: Eu editei minha edição para enfatizar melhor que esses resultados defeituosos tiveram efeitos muito positivos. Se você acha que isso ainda é ofensivo, não me importo de remover minhas edições.
27411 Sylvain
2
@Suresh: Sim, acho que a pergunta não deveria ter sido feita; Eu já comentei a pergunta e votei para fechar.
Respostas:
Um caso é o artigo STOC '88 de Blum-Feldman-Micali . A falha foi apontada por Mihir Bellare (comunicação privada). Você pode encontrar a discussão relevante aqui .
O problema de alcançabilidade da rede de Petri tem uma história rica, onde provas incompletas ou falhas levam a novos resultados. GS Sacerdote e RL Tenney apresentaram uma prova incompleta de decidibilidade no STOC '77 , o que foi fundamental para a prova posterior de EW Mayr no STOC '81 e sua melhoria por SR Kosaraju no STOC '82 . Essas provas de decidibilidade não vinham com limites superiores de complexidade (eles empregam quase pedidos ordenados para rescisão). Z. Bouziane mais tarde afirmou ter encontrado um algoritmo 2ExpSpace no FOCS '98 . Uma falha foi apontada por P. Jančar (e finalmente publicada em uma nota), mas o trabalho de Bouziane ajudou a renovar o interesse nessa antiga questão. Embora ainda não haja limites superiores conhecidos sobre a complexidade desse problema, J. Leroux apresentou recentemente uma nova prova de decidibilidade no POPL '11 .
Não em STOC / FOCS:
Outro caso aconteceu na conferência Structure in Complexity Theory (1988) (se não me engano, agora é chamada Conference on Computational Complexity.) O título do artigo era Sobre o poder de protocolos interativos de várias potências . Dois anos depois, os autores (Fortnow, Rompel e Sipser) publicaram um artigo de duas páginas "Erratas para o poder dos protocolos interativos de múltiplos provedores" na mesma conferência. Infelizmente, o IEEE não oferece este documento para download.
fonte