I am sure that every one of the readers of this blog heard about Laci Babai’s quasi-polynomial algorithm for graph isomorphism and also the recent drama about it: A mistake pointed out by Harald Helfgott, a new sub-exponential but not quasi-polynomial version of the algorithm that Laci found in a couple of days, and then, a week later, a new variant of the algorithm again found by Laci which is quasi-polynomial. You can read the announcement on Babai’s homepage, three excellent Quanta magazine articles by Erica Klarreich (I,II,III), Blog posts over Harald’s blog (III,II,I) with links to the video and article (in French), and many blog posts all over the Internet (GLL4,GLL3,GLL2,GLL1,…).
Babai’s result is an off-scale scientific achievement, it is wonderful in many respects, and I truly admire and envy Laci for this amazing breakthrough. I also truly admire Harald for his superb job as a Bourbaki expositor.
Laci Babai is visiting and he is giving lectures on graph isomorphism and related topics all over the Israel.
Tel Aviv University
Tel Aviv University: Sackler distinguished lectures in Pure Mathematics Wednesday, January 18 (Poster. Sorry, too late, I heard it was very inspiring, don’t miss the other talks!)
Tel Aviv University Combinatorics seminar: Sunday, Jan. 22, 10:00-11:00, Location: Melamed (Shenkar building, ground floor, room 6)
Title: Canonical partitioning and the emergence of the Johnson graphs: Combinatorial aspects of the Graph Isomorphism problem
(The talk does not depend on Wednesday’s talk)
Hebrew University of Jerusalem
Hebrew University Colloquium San. Jan 22, 16:00-17:00 Title: Graph isomorphism and coherent configurations: The Split-or-Johnson routine
Lecture room 2, Manchester building (Mathematics)
Local versus global symmetry and the Graph Isomorphism problem I–III
Lecture I: Monday, January 23, 2017 at 15:30
Lecture II: Tuesday, January 24, 2017 at 15:30
Lecture III: Thursday, January 26, 2017 at 15:30
All lectures will take place at Auditorium 232, Amado Mathematics Building, Technion (Website)
Pekeris lecture, Jan 29, 11:00-12:00 Hidden irregularity versus hidden symmetry
EBNER AUDITORIUM (webpage)