Algorithms & Randomness Center (ARC)

Xiaorui Sun (Microsoft Research)

Monday, March 12, 2018

Klaus 1116 East - 11am

Title:   The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds

Abstract:   

We study the edge query complexity of graph isomorphism in the property testing model for dense graphs. We give an algorithm that makes n^{1+o(1)} queries, improving on the previous best bound of O~(n^{5/4}). Since the problem is known to require \Omega(n) queries, our algorithm is optimal up to a subpolynomial factor.

While trying to extend a known connection to distribution testing, discovered by Fischer and Matsliah (SICOMP 2008), one encounters a natural obstacle presented by sampling lower bounds such as the $\Omega(n^{2/3})$-sample lower bound for distribution closeness testing (Valiant, SICOMP 2011). In the context of graph isomorphism testing, these bounds lead to an $n^{1+\Omega(1)}$ barrier for Fischer and Matsliah's approach. We circumvent these limitations by exploiting a geometric representation of the connectivity of vertices. An approximate representation of similarities between vertices can be learned with a near-linear number of queries and allows relaxed versions of sampling and distribution testing problems to be solved more efficiently.

Joint work with Krzysztof Onak

--------------------------------------

Speaker's webpage

Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836

Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu