# How to cite Babai's new graph isomorphism result?

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.
• 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. – Joshua Grochow Mar 18 '17 at 23:54
• You can write "Babai has announced an algorithm ...." and give a pointer to his website. – Chandra Chekuri Mar 19 '17 at 2:50
• 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. – Kaveh Mar 19 '17 at 18:59
• 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. – Kaveh Mar 19 '17 at 19:14
• @Kaveh I totally agree with Kaveh's point of view. – Tayfun Pay Mar 20 '17 at 3:33