- A Near-Optimal Algorithm fo...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in July 2014

## A Near-Optimal Algorithm for Testing Isomorphism of Two Unknown Graphs

**Speaker:**
Krzysztof Onak
, IBM TJ Watson Research Center

**Date:**
Wednesday, July 23, 2014

**Time:**
11:00 AM to 12:00 PM
** Note: all times are in the Eastern Time Zone**

**Public:**
Yes

**Location:**
32-D463

**Event Type:**

**Room Description:**

**Host:**
Ronitt Rubinfeld, CSAIL

**Contact:**
Ronitt Rubinfeld, ronitt@csail.mit.edu

**Speaker URL:**
None

**Speaker Photo:**

None

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

**Reminder Subject:**
TALK: A Near-Optimal Algorithm for Testing Isomorphism of Two Unknown Graphs

The goal of the graph isomorphism problem is to check if two finite graphs are identical if their labels are ignored. Apart from practical applications such as chemical compound identification and circuit verification, the problem is interesting due to its challenging open computational status.

In the property testing framework, Fischer and Matsliah (SICOMP 2008) showed that the number of queries necessary to (approximately) test isomorphism of two unknown graphs in the dense graph model is at least Omega(n) and at most O(n^(5/4)). We essentially close this gap by showing an algorithm that makes n * 2^O(sqrt(log n)) queries.

Distribution testing (Batu et al. [JACM 2013]; Batu et al. [FOCS 2001]) is one of the main tools in this line of research. A major obstacle in the quest for an efficient graph isomorphism tester turns out to be the Omega(n^(2/3)) distribution testing lower bound due to Valiant (SICOMP 2011). We bypass this lower bound by designing a more efficient algorithm that for two distributions on near-isomorphic sets of points is required to reject only if the Earth-Mover Distance between them is large.

Joint work with Xiaorui Sun (Columbia University).

**Research Areas:**

**Impact Areas:**

Created by Ronitt Rubinfeld at Tuesday, July 22, 2014 at 1:48 PM.