Tag Archives: graph isomorphism

Pilsen, days 5 and 6

So the conference is over; but before I start a description of the last two days, let me pose a problem which might be an interesting small research topic for someone. As I have said, statisticians love symmetric real matrices. … Continue reading

Posted in events | Tagged , , , , | 2 Comments

Pilsen, days 1 and 2

The conference on “Symmetry vs Regularity” in Pilsen has begun. I hesitate at trying to describe the talks, since the first day alone had 13 talks, and the second day 19, of lengths ranging from ten minutes to an hour, … Continue reading

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

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 , , , , , , , | 1 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