Wie kann man Babais neues Ergebnis des Graph-Isomorphismus zitieren?

16

Kürzlich hat Babai auf der STOC 2016 einen Aufsatz veröffentlicht, in dem behauptet wird, dass der Graphisomorphismus in quasipolynomialer Zeit gelöst werden kann.

Anfang 2017 hat Babai die quasipolynomiale Behauptung aufgrund einiger schwerwiegender Fehler von Harald Helfgott zurückgezogen. Wie Babai selbst erklärte, macht dieser Fehler die Verbesserung in Bezug auf die Laufzeit bescheidener.

Ungefähr 5 Tage nach dem Zurückziehen der Quasi-Polynom-Behauptung veröffentlichte Babai ein weiteres Update auf seiner Homepage mit der Begründung, dass er den Fehler im Beweis behoben und auf diese Weise die Quasi-Polynom-Laufzeit wiederhergestellt habe.

Ich muss sagen, dass ich nach dieser schnellen Änderung des Status der Korrektheit des Beweises das neue Papier normalerweise völlig ignorieren würde, bis es in einer angesehenen Zeitschrift veröffentlicht wurde.

Aber da Babai Babai ist, nimmt der Großteil der Gemeinde sein Wort für selbstverständlich, zumindest öffentlich, obwohl die neue Version des Papiers mit allen vorgenommenen Korrekturen nicht einmal verfügbar ist. Beachten Sie, dass selbst große Leute Fehler machen und es eine nicht zu vernachlässigende Chance gibt, dass die neue Korrektur auch einen Fehler aufweist und so weiter.

Wie soll ich nun das neue Ergebnis zitieren?

  1. Zitieren Sie das STOC-Papier mit der Behauptung, dass das Quasipolynom nach oben gebunden ist.
  2. Zitieren Sie das STOC-Papier und erklären Sie, dass es einen schwerwiegenden Fehler aufweist und dass die tatsächliche Laufzeit die vorherige subexponentielle Untergrenze verbessert.
  3. Zitieren Sie das STOC-Papier, das besagt, dass es einen Fehler hatte, der von Babai behoben wurde.
  4. Zitieren Sie überhaupt nicht und geben Sie die alte Obergrenze von als aktuell festgelegte Obergrenze.2O(n)
graph-isomorphism Nobo Dy
quelle
8
Ich würde denken, (1) wäre eine schlechte Option - vorausgesetzt, dass der Fehler als richtig herausgestellt und anerkannt wurde (das heißt, der ursprüngliche Fehler wurde nicht bestritten, sondern vom Autor bestätigt), tut Option (1) dies nicht entsprechen nicht den derzeit besten verfügbaren Informationen. Neben 2-4 gibt es auch andere Optionen - z. B. Sie könnten einfach vollständige Informationen angeben (die ganze Geschichte wie oben), oder Sie könnten die STOC-Version zitieren, aber sagen, dass eine vollständige, von Fachleuten geprüfte Version mit der Korrektur des bekannten Fehlers dies nicht getan hat noch erschienen, und zitieren Sie die bisher besten gebundenen sowie.
Joshua Grochow
7
Sie können schreiben "Babai hat einen Algorithmus angekündigt ..." und einen Hinweis auf seine Website geben.
Chandra Chekuri
3
Kommt darauf an, warum du seine Zeitung zitierst. Wenn Sie ein Ergebnis haben, das auf seinem aufbaut, können Sie Ihr Ergebnis als bedingt einstufen und dann seine Arbeit zitieren, wie Chandra schrieb. Wenn Sie es zitieren, aber nicht verwenden, können Sie es erneut zitieren, wie Chandra es geschrieben hat. In beiden Fällen auf seinen Posten oder / und seinen Entwurf verlinken. Jeder Interessierte kann selbst überprüfen, ob es richtig ist oder nicht.
Kaveh
7
Übrigens denke ich nicht, dass Babai anders behandelt wird als andere Experten in ihren Fachgebieten, und dass ein Teil Ihrer Stelle sich nicht mit der Frage befasst, wie ein Anspruch oder ein Entwurfspapier zu zitieren ist, der noch geprüft wird. Dadurch sieht Ihr Beitrag wie eine Beschwerde aus, daher würde ich vorschlagen, ihn zu entfernen. Der Unterschied in der Behandlung zu unbekannten zufälligen Personen, die kein wichtiges Ergebnis auf dem Gebiet veröffentlicht haben und daher noch keine Fachkenntnisse auf dem Gebiet nachweisen müssen, ist wie in jedem anderen Fall gerechtfertigt.
Kaveh
@Kaveh Ich stimme Kavehs Standpunkt voll und ganz zu.
Tayfun Pay

Antworten:

5

Zuallererst würde ich davon abraten, eine bedingungslose Arbeit zur Veröffentlichung einzureichen, die vom quasi-polynomialen Ergebnis abhängt. Formulieren Sie das Ergebnis als Bedingung für die Existenz eines quasi-polynomialen GI-Algorithmus und geben Sie in einer Fußnote an, dass Babai dies möglicherweise bewiesen hat, das Papier jedoch nicht öffentlich verfügbar ist. In diesem Fall ist kein Zitieren erforderlich, da Sie das Ergebnis für das Papier nicht benötigen.

In jedem anderen Zusammenhang halte ich es nicht für besonders notwendig, ein verfügbares Papier zu zitieren - das Zitieren seiner Website ist in Ordnung. Es hängt ein wenig davon ab, was Sie schreiben, aber ich würde empfehlen, etwas in der Art von "zu behaupten, es wird allgemein angenommen, dass GI in quasipolynomialer Zeit lösbar ist, und ein Beweis dafür wurde von Laszlo Babai [Zitat auf der Webseite, wo er macht den Anspruch]. "

Ein bemerkenswerter Vorteil des Zitierens seiner Online-Behauptung ist, dass seine Website sowohl seine eigenen Worte zur aktuellen Behauptung als auch einen Link zu seinem Vordruck enthält.

Stella Biderman
quelle
6
(Ich habe auch nicht abgelehnt.) Ich bin mir nicht sicher, ob ich mir sicher bin, dass die erste Hälfte Ihres Satzes (es wird allgemein angenommen, dass GI in QP ist) vor Babais Ankündigung wahr war. Ich denke, vor Babais Ankündigung war sogar die Meinung darüber, ob GI in der QP war, mehr geteilt als etwa die Meinung über P gegen NP (nur als Vergleich für etwas "weit verbreitetes"). Nach Babais Ankündigung ist die Meinung, ob GI
Joshua Grochow am