Comment citer le nouveau résultat d'isomorphisme du graphe de Babai?

16

Récemment, Babai a publié un article sur le STOC 2016 affirmant que l'isomorphisme des graphes peut être résolu en temps quasi-polynomial.

Au début de 2017, Babai a rétracté la réclamation quasi-polynomiale en raison de graves erreurs trouvées par Harald Helfgott. Comme expliqué par Babai lui-même, cette faille rend l'amélioration plus modeste en termes de durée de fonctionnement.

Environ 5 jours après avoir retiré la réclamation quasi-polynomiale, Babai a publié une autre mise à jour sur sa page d'accueil, arguant qu'il avait corrigé le défaut de la preuve, rétablissant ainsi le temps d'exécution quasi-polynomial.

Je dois dire qu'après ce changement rapide du statut de l'exactitude de la preuve, j'ignorerais complètement le nouveau papier jusqu'à ce qu'il soit publié dans une revue très respectée.

Mais puisque Babai est Babai, la plupart de la communauté tient sa parole pour acquise, au moins publiquement, même si la nouvelle version du document avec toutes les corrections implémentées n'est même pas disponible. Notez que même les gens formidables font des erreurs et il y a une chance non négligeable que le nouveau correctif présente également un défaut, etc.

Alors maintenant, comment dois-je citer le nouveau résultat?

  1. Citez le document du STOC revendiquant le quasipolynôme supérieur.
  2. Citez le document du STOC expliquant qu'il a un grave défaut et que le temps de fonctionnement réel améliore la borne inférieure subexponentielle précédente.
  3. Citez le journal du STOC disant qu'il y avait un défaut qui a été corrigé par Babai.
  4. Ne citez pas du tout et indiquez l'ancienne limite supérieure de comme limite supérieure actuellement établie.2O(n)
graph-isomorphism Personne
la source
8
Je pense que (1) serait une mauvaise option - étant donné que la faille a été signalée et reconnue comme correcte (c'est-à-dire que la faille d'origine n'a pas été contestée, mais a plutôt été reconnue par l'auteur), l'option (1) ne fonctionne pas ne reflètent pas les meilleures informations actuellement disponibles. Outre 2-4, il existe également d'autres options - par exemple, vous pouvez simplement donner des informations complètes (toute l'histoire comme ci-dessus), ou vous pouvez citer la version STOC mais dire qu'une version complète évaluée par les pairs avec la correction du défaut connu n'a pas encore paru, et cite également la meilleure limite précédente.
Joshua Grochow
7
Vous pouvez écrire "Babai a annoncé un algorithme ...." et donner un pointeur sur son site Web.
Chandra Chekuri
3
Cela dépend de la raison pour laquelle vous citez son article. Si vous avez un résultat qui s'appuie sur le sien, vous pouvez faire du vôtre un conditionnel, puis citer son article comme l'écrivait Chandra. Si vous le citez mais ne l'utilisez pas, vous pouvez à nouveau le citer comme l'a écrit Chandra. Dans les deux cas, un lien vers son poste ou / et son brouillon. Toute personne intéressée peut vérifier si elle est correcte ou non pour elle-même.
Kaveh
7
Btw Je ne pense pas que Babai soit traité différemment des autres experts dans leurs domaines d'expertise, cette partie de votre message n'est pas relancée à la question de savoir comment citer une revendication ou un projet de document qui est toujours en cours d'examen. Votre message ressemble à une plainte, je vous suggère donc de le supprimer. La différence de traitement par rapport à des personnes aléatoires inconnues qui n'ont publié aucun résultat important sur le terrain et qui n'ont donc pas encore prouvé d'expertise dans le domaine est justifiée comme ailleurs.
Kaveh
@Kaveh Je suis totalement d'accord avec le point de vue de Kaveh.
Tayfun Payez

Réponses:

5

Tout d'abord, je découragerais de soumettre pour publication un article inconditionnel qui dépend du résultat quasi polynomial, si c'est pour cela que vous voulez la citation. Reformulez le résultat en fonction de l'existence d'un algorithme GI quasi polynomial et indiquez dans une note de bas de page que Babai a peut-être prouvé cela, mais que le document n'est pas accessible au public. Dans ce cas, aucune citation n'est nécessaire car vous n'avez pas besoin du résultat pour le papier.

Dans tout autre contexte, je ne pense pas qu'il soit particulièrement nécessaire de citer un document disponible - citer son site Web est très bien. Cela dépend un peu de ce que vous écrivez, mais je recommanderais d'affirmer quelque chose dans le sens de "il est largement admis que l'IG est résoluble en temps quasi-polynomial et une preuve en a été annoncée par Laszlo Babai [citation de la page Web où il fait la réclamation]. "

Un avantage notable de citer sa réclamation en ligne est que son site Web contient à la fois ses propres mots concernant la réclamation actuelle et un lien vers sa préimpression.

Stella Biderman
la source
6
(Je n'ai pas non plus dévalué.) Je ne suis pas sûr d'acheter que la première moitié de votre phrase (on pense généralement que GI est en QP) était vraie avant l'annonce de Babai. Je pense qu'avant l'annonce de Babai, même l'opinion sur la question de savoir si GI était dans QP était probablement plus divisée que, disons, les opinions sur P vs NP (juste comme point de comparaison pour quelque chose de "largement cru"). Après l'annonce de Babai, je pense que l'opinion est toujours divisée sur la question de savoir si GI va finir en P.
Joshua Grochow