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

DOI10.1145/3188745.3188952MaRDI QIDQ5230286zbMATH OpenOpenAlexFDO

Authors 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

samplingquery complexitygraph isomorphismproperty testing

Mathematics Subject Classification ID

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

Recommendations

• Testing Graph Isomorphism
• Nearly tight bounds for testing function isomorphism
• The difficulty of testing for isomorphism against a graph that is given in advance
• Nearly tight bounds for testing function isomorphism
• The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance

Cited in

(7)

• Testing distributions of huge objects
• On the generic complexity of the searching graph isomorphism problem
• The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance
• Lower bounds for approximating graph parameters via communication complexity
• Distributed Testing of Graph Isomorphism in the CONGEST Model.
• The difficulty of testing for isomorphism against a graph that is given in advance
• Testing Graph Isomorphism

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230286)