Reductions to graph isomorphism

DOI10.1007/S00224-008-9159-1zbMATH Open1205.68167OpenAlexW2005365874MaRDI QIDQ987394FDOQ987394

Authors: Jacobo Torán 

Publication date: 13 August 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-008-9159-1

Recommendations

• Reductions to Graph Isomorphism
• On the Hardness of Graph Isomorphism
• scientific article; zbMATH DE number 512806
• scientific article; zbMATH DE number 4007728
• Graph isomorphism is not \(\mathsf{AC}^{0}\)-reducible to group isomorphism

zbMATH Keywords

computational complexitygraph isomorphismreducibilities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)

Cites Work

• Space-bounded hierarchies and probabilistic computations
• On uniform circuit complexity
• On uniformity within \(NC^ 1\)
• A taxonomy of problems with fast parallel algorithms
• On the Hardness of Graph Isomorphism
• Group-theoretic algorithms and graph isomorphism
• Completeness results for graph isomorphism.
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• On the Decomposability of $NC$ and $AC$
• Adaptive logspace reducibility and parallel time
• Graph isomorphism is low for PP
• Promise problems complete for complexity classes
• Equivalence of NC\(^ k\) and AC\(^{k-1}\) closures of NP and other classes

Cited In (13)

• Graph isomorphism is not \(\mathsf{AC}^{0}\)-reducible to group isomorphism
• Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
• Reductions to Graph Isomorphism
• Graph isomorphism is not \(\mathrm{AC}^0\) reducible to group isomorphism
• Title not available (Why is that?)
• A method of graph reduction and its applications
• Title not available (Why is that?)
• On the reduction of Yutsis graphs
• Graph isomorphism is low for PP
• CNF and DNF succinct graph encodings
• Title not available (Why is that?)
• On the Hardness of Graph Isomorphism
• The complexity of homomorphism factorization

This page was built for publication: Reductions to graph isomorphism

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