17
$\begingroup$

Recently, Babai has published a paper on STOC 2016 claiming that graph isomorphism can be solved in quasipolynomial time.

In the beginning of 2017, Babai retracted the quasipolynomial claim due to some serious mistakes found by Harald Helfgott. As explained by Babai himself, this flaw makes the improvement more modest in terms of running time.

About 5 days after retracting the quasi-polynomial claim, Babai posted another update in his homepage arguing that he had fixed the flaw in the proof, restoring in this way the quasi-polynomial running time.

I have to say that after this fast change on the status of the correctness of the proof I would normally completely ignore the new paper until it was published in a well respected journal.

But since Babai is Babai, most of the community is taking his's word for granted, at least publicly, even though the new version of the paper with all corrections implemented is not even available. Note that even great people make mistakes and there is a non-negligible chance that the new fix also has a flaw and so on.

So now, how should I cite the new result?

  1. Cite the STOC paper claiming the quasipolynomial upperbound.
  2. Cite the STOC paper explaining that it has a serious flaw and that the real running time improves the previous subexponential lower bound.
  3. Cite the STOC paper saying that it had a flaw that was fixed by Babai.
  4. Do not cite at all, and state the old upper bound of $2^{O(\sqrt{n})}$ as the current established upper bound.
Improve this question
$\endgroup$
5
  • 9
    $\begingroup$ I would think (1) would be a bad option - given that the flaw was pointed out and acknowledged as correct (that is, the original flaw wasn't contested, but rather was acknowledge, by the author), option (1) doesn't reflect the currently best available information. Besides 2-4, there are other options too - e.g. you could just give complete information (the whole story as above), or you could cite the STOC version but say a full peer-reviewed version with the fix of the known flaw has not yet appeared, and cite the previous-best bound as well. $\endgroup$
    – Joshua Grochow
    Mar 18, 2017 at 23:54
  • 7
    $\begingroup$ You can write "Babai has announced an algorithm ...." and give a pointer to his website. $\endgroup$
    – Chandra Chekuri
    Mar 19, 2017 at 2:50
  • 3
    $\begingroup$ Depends on why you are citing his paper. If you have a result that builds upon his you can make yours a conditional one and then cite his paper as Chandra wrote. If you are citing it but not using it you can again cite it as Chandra wrote. In both cases link to the his post or/and his draft. Anyone interested can check if it is correct or not for themselves. $\endgroup$
    – Kaveh
    Mar 19, 2017 at 18:59
  • 8
    $\begingroup$ Btw I don't think Babai is treated any differently from other experts in their fields of expertise, that part of the your post is not relent to the question of how to cite a claim or draft paper that is still under review. It makes your post look like a complaint so I would suggest removing it. The difference in treatment compared to unknown random people who have not published any important result in the field and therefore are yet to prove any expertise in the field is justified as in any where else. $\endgroup$
    – Kaveh
    Mar 19, 2017 at 19:14
  • $\begingroup$ @Kaveh I totally agree with Kaveh's point of view. $\endgroup$
    – Tayfun Pay
    Mar 20, 2017 at 3:33

1 Answer 1

Reset to default
6
$\begingroup$

First off, I would discourage submitting for publication an unconditional paper which depends on the quasi-polynomial result, if that's what you want the citation for. Rephrase the result as conditional upon the the existence of a quasi-polynomial GI algorithm and state in a footnote that Babai may have proven this but that the paper is not publicly available. In this case, no citation is necessary because you don't need the result for the paper.

In any other context, I don't think it's particularly necessary to cite an available paper - citing his website is fine. It depends a little on what you are writing, but I would recommend asserting something along the lines of "it is widely believed that GI is solvable in quasipolynomial time and a proof of this has been announced by Laszlo Babai [citation to the webpage where he makes the claim]."

One notable advantage of citing his online claim is that his website contains both his own words as to the current claim and a link to his preprint.

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ (I didn't downvote either.) I'm not so sure I buy that the first half of your sentence (it is widely believed that GI is in QP) was true before Babai's announcement. I think before Babai's announcement, even opinion on whether GI was in QP was probably more divided than, say, opinions on P vs NP (just as a point of comparison for something "widely believed"). After Babai's announcement, I think opinion is still divided on whether GI will end up in P. $\endgroup$
    – Joshua Grochow
    Mar 22, 2017 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.