Atlantic Graph Theory Seminar: Ben Moore – Oct 29
October 29, 2025 @ 3:30 pm - 4:30 pm
Date and Time: Wednesday, October 29, 3.40 pm Atlantic time
Speaker: Ben Moore, University of Manitoba
Title: Smoothed analysis for graph isomorphism
Abstract: I’ll describe a simple algorithm which shows the following: Given any graph G, add or remove edges uniformly at random with probability 100/v(G) to create a graph G’. We can test in polynomial time if G’ is isomorphic to any other graph H. In other words, graph isomorphism is in P if you add a little bit of randomness to the instance.
Joint work with: Michael Anastos and Matthew Kwan.
Zoom link:
https://us02web.zoom.us/j/88013261876?pwd=XGocyHqvseXY8metPztPoSuulEEejX.1
Meeting ID: 880 1326 1876
Passcode: 357963