Tag Archives: graph isomorphism

Symmetry vs Regularity

This is the title of a conference to be held next year (2018) from 1 to 7 July, in Pilsen, Bohemia, Czech Republic. The subtitle is “The first 50 years since Weisfeiler-Leman stabilization”, and the webpage is here. If you … Continue reading

Posted in events, exposition | Tagged , , , , , , , | Leave a comment

All kinds of mathematics, 4

The fourth day began with a talk by László Babai on his quasi-polynomial algorithm for graph isomorphism. Two longer and more detailed accounts were scheduled for the workshop; this talk gave the context, and an important lemma which underlies the … Continue reading

Posted in events | Tagged , , , , , , | Leave a comment

Update on Babai’s result

I learned yesterday that Harald Helfgott had found a mistake in László Babai’s result on the complexity of graph isomorphism. The algorithm and the bulk of the analysis still stands; it was just problem with the accounting showing that the … Continue reading

Posted in Uncategorized | Tagged , , | Leave a comment

Graph isomorphism

I just read Ken Regan’s report on the Gödel’s Last Letter blog that Laci Babai has a quasi-polynomial algorithm for graph isomorphism “Quasi-polynomial” means exp(O((log n)c)) for some c: c = 1 would be polynomial. Congratulations Laci! Oh, and here he is at … Continue reading

Posted in Uncategorized | Tagged , | 2 Comments