The query complexity of graph isomorphism: bypassing distribution testing lower bounds

DOI10.1145/3188745.3188952zbMath1428.68390OpenAlexW2794200891MaRDI QIDQ5230286

Krzysztof Onak, Xiaorui Sun

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3188745.3188952

zbMATH Keywords

samplingproperty testingquery complexitygraph isomorphism

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

Distributed Testing of Graph Isomorphism in the CONGEST Model.

This page was built for publication: The query complexity of graph isomorphism: bypassing distribution testing lower bounds