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

graph isomorphismproperty testingquery complexitysampling

Mathematics Subject Classification ID

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

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

(8)

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

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)