A Near-Optimal Algorithm for Testing Isomorphism of Two Unknown Graphs
, 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
Host: Ronitt Rubinfeld, CSAIL
Contact: Ronitt Rubinfeld, email@example.com
Speaker URL: None
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).
Created by Ronitt Rubinfeld at Tuesday, July 22, 2014 at 1:48 PM.