Oberlin College and Conservatory

The graph isomorphism problem

Monday, February 26, 2018 at 4:30pm to 5:30pm

King Building, 241
10 North Professor Street, Oberlin, OH 44074

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

Event Type

Lectures/Symposia/Workshops

Departments

Academic, Computer Science

Contact Person

Jackie Fortino

Contact Phone Number

440 775-8043

Contact E-mail Address

jackie.fortino@oberlin.edu

Subscribe
Google Calendar iCal Outlook

Recent Activity