Harald Andrés Helfgott, Alexander von Humboldt Professor at the University of Göttingen in Germany, will speak on "The graph isomorphism problem."
Suppose we are given two graphs with sets of vertices of the same size. Are the graphs isomorphic? That is, is there a bijection between the two sets of vertices identifying the two graphs? There may be more than one such bijection ('isomorphism"). Can we describe them all?
The challenge ("graph isomorphism problem") is to give a polynomial-time algorithm that always succeeds in answering these questions. László Babai (U. Chicago) has recently shown how to answer these questions - and several related ones - in quasipolynomial time, i.e., in time at most exp((log n)^C), C a constant. His strategy is based in part on work by Luks (1980/82), who solved the case of graphs of bounded degree, and by Weisfeiler and Leman (1968), whose early approach to the problem furnished a valueable tool.
The talk should be accessible to those who have taken a first course in group theory and have some familiarity with algorithms.
Refreshments will be served at 4 p.m. King 225