![Algorithms and Uncertainty_small text_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Algorithms%20and%20Uncertainty_hi-res_1.jpg?h=6dcb57f1&itok=7LxcepO0)
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.
All scheduled dates:
Upcoming
No Upcoming activities yet