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

DOI10.1145/3188745.3188952zbMATH Open1428.68390OpenAlexW2794200891MaRDI QIDQ5230286FDOQ5230286

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

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

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)

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)