| Title | : | Smoothed analysis for graph isomorphism |
| Speaker | : | Benjamin Moore (IST Austria) |
| Details | : | Fri, 11 Apr, 2025 2:30 PM @ SSB 233 (MR1) |
| Abstract: | : | Graph isomorphism is a notoriously hard problem whose complexity is unknown. I will show that every instance of graph isomorphism is close to an easy instance, in the following sense. Take any graph G and add or remove edges with probability 100/n. The resulting graph G' can be tested for graph isomorphism against any other graph in polynomial time.
In fact, the algorithm used is extremely simple and is implemented in practical graph isomorphism software such as Nauty. Thus, our result gives justification for why graph isomorphism is easy in practice.
This is joint work with Micheal Anastos and Matthew Kwan, and will appear in STOC 2025.
Brief Bio: Benjamin Moore is a Canadian who did a Masters in Mathematics at Simon Fraser University, and then did a PhD in the Combinatorics and Optimization Department at the University of Waterloo. After this, he was a postdoc at Charles university (Czech Republic), and is currently a postdoc at the Institute of Science and Technology, Austria. |
