Today, the ICE-TCS seminar series at Reykjavik University hosted a talk by Benjamin Moore (Institute of Science and Technology Austria) who is visiting our postdoctoral researcher Nicolaos Matsakis.
Benjamin presented the main results in his paper "Smoothed analysis for graph isomorphism", coauthored with his ISTA colleagues Michael Anastos and Matthew Kwan. (In passing, I just saw that Matthew Kwan received the main prize of the Austrian Mathematical Society last year. Congratulations!)
To my mind, Benjamin did an excellent job in presenting the context for their exciting (but very technical) contribution and the main ideas that underlie it. Kudos! The work by Benjamin and his collaborators provides another explanation of the effectiveness of the colour refinement algorithm (also known as the one-dimensional Weisfeiler-Leman algorithm) in checking whether two graphs are isomorphic. I encourage you to read at least the introduction of their paper, which will be presented at STOC 2025, and the ISTA news article here, which does a much better job at putting their work in context than an interested, but ignorant, observer like me ever could. FWIW, I find results like theirs, which offer some explanation as to why theoretically hard problems are seemingly easy in practice, fascinating and I feel like that paper might be a strong candidate for a best paper award.
It was also fitting to see recent work on smoothed analysis being presented at our seminar series since Daniel Spielman and Shang-Hua Teng received the 2008 Gödel Prize at ICALP 2008, which was held at Reykjavik University. Time flies, but great work is timeless.
By Luca Aceto
Today, the ICE-TCS seminar series at Reykjavik University hosted a talk by Benjamin Moore (Institute of Science and Technology Austria) who is visiting our postdoctoral researcher Nicolaos Matsakis.
Benjamin presented the main results in his paper "Smoothed analysis for graph isomorphism", coauthored with his ISTA colleagues Michael Anastos and Matthew Kwan. (In passing, I just saw that Matthew Kwan received the main prize of the Austrian Mathematical Society last year. Congratulations!)
To my mind, Benjamin did an excellent job in presenting the context for their exciting (but very technical) contribution and the main ideas that underlie it. Kudos! The work by Benjamin and his collaborators provides another explanation of the effectiveness of the colour refinement algorithm (also known as the one-dimensional Weisfeiler-Leman algorithm) in checking whether two graphs are isomorphic. I encourage you to read at least the introduction of their paper, which will be presented at STOC 2025, and the ISTA news article here, which does a much better job at putting their work in context than an interested, but ignorant, observer like me ever could. FWIW, I find results like theirs, which offer some explanation as to why theoretically hard problems are seemingly easy in practice, fascinating and I feel like that paper might be a strong candidate for a best paper award.
It was also fitting to see recent work on smoothed analysis being presented at our seminar series since Daniel Spielman and Shang-Hua Teng received the 2008 Gödel Prize at ICALP 2008, which was held at Reykjavik University. Time flies, but great work is timeless.