Graph Isomorphism is Not AC0-Reducible to Group Isomorphism
From MaRDI portal
Publication:2947584
DOI10.1145/2540088zbMath1322.68096OpenAlexW1981433559MaRDI QIDQ2947584
Fabian Wagner, Arkadev Chattopadhyay, Jacobo Toran
Publication date: 24 September 2015
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2540088
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (1)
This page was built for publication: Graph Isomorphism is Not AC0-Reducible to Group Isomorphism
