Uncertainty Seminar

The Query Complexity of Testing Graph Isomorphism

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. 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.