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

Presented on March 12, 2018 at 11:00 a.m. in the Klaus Advanced Computing Building, Room 1116E.Xiaorui Sun is a postdoctoral researcher at Microsoft Research Redmond. Prior to joining Microsoft, he was a Google Research Fellow at Simons Institute at UC Berkeley. His research focuses on the design and analysis of algorithms with an emphasis on big data processing, including algorithmic graph theory, massively parallel computing and machine learning theory.Runtime: 58:39 minutesWe 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 Ona