ARC Colloquium: Xiaorui Sun (Microsoft)

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


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:

Click here to subscribe to the seminar email list:


Event Details


  • Monday, March 12, 2018
    11:00 am - 12:00 pm
Location: Klaus 1116E