- GRAPH ISOMORPHISM
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in March 2014

## GRAPH ISOMORPHISM

**Speaker:**
Laszlo Babai
, University of Chicago

**Date:**
Tuesday, March 11, 2014

**Time:**
4:15 PM to 5:15 PM
** Note: all times are in the Eastern Time Zone**

**Refreshments:**
3:45 PM

**Public:**
Yes

**Location:**
32-G449

**Event Type:**

**Room Description:**

**Host:**
Ankur Moitra

**Contact:**
Holly A Jones, hjones01@csail.mit.edu

**Relevant URL:**
http://toc.csail.mit.edu/node/485

**Speaker URL:**
None

**Speaker Photo:**

None

**Reminders to:**
toc@csail.mit.edu, seminars@csail.mit.edu, theory-seminars@csail.mit.edu

**Reminder Subject:**
TALK: GRAPH ISOMORPHISM

The talk will put recent progress on algorithms for the Graph

Isomorphism (GI) problem in perspective.

GI is one of the very few classical problems in NP of unsettled

complexity status. Shortly after the introduction of group theory

to the algorithmic GI tools [B 1979], a combination of Luks's group

theoretic divide-and-conquer techniques (1980) with Zemlyachenko's

combinatorial degree reduction (1982) resulted in a "moderately

exponential" worst-case bound, exponential in $n^{1/2}$ where $n$

is the number of vertices [B-Luks, STOC 1983]. (I am ignoring

logarithmic terms in the exponent.) This bound has stood firm for

over three decades.

Progress has been made recently on the important subcase of

strongly regular (SR) graphs. The new results, obtained by five

authors, Xi Chen, Xiaorui Sun (Columbia U), and Shang-Hua Teng

(USC), partly in parallel and partly in joint work with the

speaker and his student John Wilmes (U Chicago), reduce the

exponent for SR graphs from $n^{1/3}$ [Spielman, STOC 1996]

to $n^{1/5}$ ([BW] & [CST]: STOC 2013 and [BCSTW]: FOCS 2013).

The result is based partly on an intricate analysis of the

classical combinatorial heuristic of individualization and

refinement (I/R), and partly on a combination of I/R with Luks's

group theoretic methods in the spirit of [B-Luks, 1983] and

[Miller 1983]. More recently, a mathematical obstacle to

potentially subexponentially or even quasipolynomially efficient

applications of the group theory method to SR GI has been removed,

using some spectral graph theory and elementary combinatorics

[B, ITCS 2014]. A caveat: significant combinatorial difficulties

remain in the way of realizing this potential, but promising

first steps appear in the treatment of the low-degree

cases in [BCSTW].

While these results are limited to SR graphs, a class not expected

to be GI-complete, in the speaker's view SR graphs hold some of the

key combinatorial difficulties of the general GI problem.

The talk will review the recent results and put them in perspective

from the point of view of the general GI problem. A key concept

here is that of coherent configurations (CCs), i.e., edge-colorings

of the complete directed graph satisfying certain strong regularity

constraints. These colorings are the stable configurations of the

Weisfeiler--Leman canonical refinement process (1968) and therefore

CCs are GI-complete. *Primitive* CCs are the ones where the obvious

combinatorial divide-and-conquer breaks down. Primitive CCs

generalize SR graphs. Their isomorphism can be tested, using I/R

only, in time, exponential in $n^{1/2}$ [B, Annals of Math 1981].

Breaking this barrier that has stood for a third of a century

is one of the more immediate targets related to the recent work.

**Research Areas:**

**Impact Areas:**

Created by Holly A Jones at Tuesday, March 04, 2014 at 9:57 AM.