Основные ошибки в принятых документах FOCS / STOC [закрыто]
23
Вы сталкивались с таким случаем в прошлом? Ну, есть возможность для всего, но я хотел бы знать, насколько реалистичным может быть это заболевание. Я имею в виду серьезные ошибки, изменяющие цель статьи, а не мелкие ошибки, конечно. Благодарность
Я не хотел заключать крупную сделку. Если Ланс отправит это, это хорошо :)
Суреш Венкат
5
@ N27: «Вопрос не требует списка документов», да, но иметь большой список таких ошибок гораздо полезнее. В противном случае комментарий Суреша является концом истории, поскольку он отвечает на вопрос утвердительно. Я также предлагаю изменить FOCS / STOC, чтобы разрешить другие «престижные» конференции и даже журналы.
MS Dousti
6
Я немного удивлен, что этот вопрос еще не закрыт. Все примеры таких ошибок могут быть смущающими, и мы можем оскорбить авторов, перефразируя их старые ошибки. Мы должны быть вежливы и профессиональны, и этот вопрос является просьбой об оскорблениях. Я голосую, чтобы закрыть это («не по теме» только из-за отсутствия лучшей причины).
Юкка Суомела
4
Я согласен с Юккой в этом. Виртуальный голос, чтобы закрыть.
Дейв Кларк,
Ответы:
10
Одним из случаев является статья STOC '88 Блюма-Фельдмана-Микали . На них указал Михир Белларе (личное сообщение). Вы можете найти соответствующую дискуссию здесь .
Проблема достижимости сети Петри имеет богатую историю, где неполные или ошибочные доказательства позже приводят к новым результатам. GS Sacerdote и RL Tenney представили неполное доказательство решимости на STOC '77 , что, однако, сыграло важную роль в более позднем доказательстве EW Mayr на STOC '81 и его улучшении С. Р. Косараю на STOC '82 . Эти доказательства разрешимости не сопровождаются верхними границами сложности (они хорошо используют квазиупорядочения для завершения). Позже Z. Bouziane утверждал, что нашел алгоритм 2ExpSpace на FOCS '98 . Дефект был отмечен П. Jančar (и , наконец , опубликован в примечании), но работа Бузиана помогла возобновить интерес к этому старому вопросу. Хотя до сих пор нет известных верхних границ сложности этой проблемы, Ж. Леру недавно представил новое доказательство разрешимости на POPL '11 .
Не в STOC / FOCS:
Еще один случай произошел на конференции Structure in the сложная теория (1988) (если я не ошибаюсь, сейчас она называется Конференция по вычислительной сложности). Заголовок статьи был « О мощи многоуровневых интерактивных протоколов» . Два года спустя авторы (Fortnow, Rompel и Sipser) опубликовали на той же конференции двухстраничную статью «О возможностях интерактивных протоколов с несколькими доказательствами». К сожалению, IEEE не предлагает этот документ для скачивания.
@ Андрас: Да. Более того, тезис Fortnow охватывает это. @Jukka: Мой оригинальный ответ был позже отредактирован. Я не могу комментировать отредактированный ответ, но в части ответа, которую я написал, ваша точка зрения не относится. Это потому, что люди, которые изначально написали (ошибочную) статью, позже указали на недостатки в своей оригинальной статье и исправили их. Поэтому нет проблем упоминать их здесь.
MS Dousti
1
@ Садек: Считаете ли вы, что если люди уже прошли через затруднение публикации ошибочного результата, а затем опубликовали исправление своей ошибки, они будут рады видеть, что этот старый инцидент перефразирован и опубликован здесь снова? Разве вы не видите причин быть немного более осторожными и внимательными? Конечно, очень хорошо вежливо упомянуть об ошибке, если у кого-то есть технический вопрос, связанный с конкретной проблемой, но в этом вопросе, похоже, единственная цель состоит в том, чтобы собрать какой-то зал позора, без веской причины, просто удовлетворить любопытство.
Юкка Суомела
2
Но тогда весь этот вопрос не следует задавать, верно? может быть, время для мета-обсуждения.
Суреш Венкат
2
@Jukka: я отредактировал свое редактирование, чтобы лучше подчеркнуть, что эти ошибочные результаты имели очень положительные эффекты. Если вы думаете, что это все еще оскорбительно, я не против удалить свои правки.
Сильвен
2
@ Суреш: Да, я думаю, что вопрос не должен был быть задан; Я уже прокомментировал вопрос и проголосовал за закрытие.
Ответы:
Одним из случаев является статья STOC '88 Блюма-Фельдмана-Микали . На них указал Михир Белларе (личное сообщение). Вы можете найти соответствующую дискуссию здесь .
Проблема достижимости сети Петри имеет богатую историю, где неполные или ошибочные доказательства позже приводят к новым результатам. GS Sacerdote и RL Tenney представили неполное доказательство решимости на STOC '77 , что, однако, сыграло важную роль в более позднем доказательстве EW Mayr на STOC '81 и его улучшении С. Р. Косараю на STOC '82 . Эти доказательства разрешимости не сопровождаются верхними границами сложности (они хорошо используют квазиупорядочения для завершения). Позже Z. Bouziane утверждал, что нашел алгоритм 2ExpSpace на FOCS '98 . Дефект был отмечен П. Jančar (и , наконец , опубликован в примечании), но работа Бузиана помогла возобновить интерес к этому старому вопросу. Хотя до сих пор нет известных верхних границ сложности этой проблемы, Ж. Леру недавно представил новое доказательство разрешимости на POPL '11 .
Не в STOC / FOCS:
Еще один случай произошел на конференции Structure in the сложная теория (1988) (если я не ошибаюсь, сейчас она называется Конференция по вычислительной сложности). Заголовок статьи был « О мощи многоуровневых интерактивных протоколов» . Два года спустя авторы (Fortnow, Rompel и Sipser) опубликовали на той же конференции двухстраничную статью «О возможностях интерактивных протоколов с несколькими доказательствами». К сожалению, IEEE не предлагает этот документ для скачивания.
источник