The query complexity of graph isomorphism: bypassing distribution testing lower bounds
Krzysztof Onak, Xiaorui Sun · 2018
We study the query complexity of graph isomorphism in the property testing model for dense graphs. We give an algorithm that makes n1+o(1) queries, improving on the previous best bound of Õ(n5/4). Since the problem is known to require Ω(n) queries, our algorithm is optimal up to a subpolynomial factor.