Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

New for: D2, D3, D4, D5
<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:The Isomorphism Problem for Highly Regular Combinatorial Objects
Speaker:John Wilmes
coming from:University of Chicago
Speakers Bio:
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Monday, 14 December 2015
Please note: New Time!
Duration:30 Minutes
Building:E1 4
The Graph Isomorphism problem has been notorious in computational

complexity theory for its unresolved complexity status. Families of
graphs characterized by high degrees of regularity, such as strongly
regular graphs (SRGs), have been viewed as particularly difficult cases.
In joint work with Babai, Chen, Sun, and Teng, we give new
time-complexity bounds for SRG Isomorphism, including the first
quasipolynomial bound in a range of the parameters. Our overall
exp(O~(n^{1/5})) time-complexity bound improved Spielman’s
exp(O~(n^{1/3})) time-complexity bound established in 1996.

Primitive coherent configurations (PCCs) generalize SRGs. PCCs appear in
Babai’s recent quasipolynomial-time algorithm for Graph Isomorphism as
combinatorial obstacles that must be overcome. In joint work with Sun,
we give an exp(O~(n^{1/3}))-time algorithm for PCC Isomorphism,
improving the previous best exp(O~(n^{1/2}))-time algorithm, due to
Babai in 1981.

In this talk, we will give an overview of progress on the isomorphism
problem for highly regular combinatorial objects, explain some of the
combinatorial structure theory underlying our analysis, and describe the
connections between these results and Babai’s recent breakthrough.

Name(s):Christina Fries
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Uwe Brahm, 12/14/2015 10:44 AM
  • Christina Fries, 12/14/2015 08:57 AM
  • Christina Fries, 12/09/2015 03:24 PM
  • Christina Fries, 12/09/2015 03:20 PM -- Created document.