Graph isomorphism is not AC^0 reducible to group isomorphism

DOI10.4230/LIPICS.FSTTCS.2010.317MaRDI QIDQ2908861zbMATH OpenOpenAlexFDO

Authors Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner

Publication date 29 August 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_bb62.html

zbMATH Keywords

circuit com plexitycomplexitygroup isomorphism problem

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Graph isomorphism is not \(\mathsf{AC}^{0}\)-reducible to group isomorphism
• On the Hardness of Graph Isomorphism
• Reductions to Graph Isomorphism
• Reductions to graph isomorphism
• Graph isomorphism in quasipolynomial time (extended abstract)

Cited in

(8)

• Nondeterministics circuits, space complexity and quasigroups
• On isomorphism testing of groups with normal Hall subgroups
• Graph isomorphism is not \(\mathsf{AC}^{0}\)-reducible to group isomorphism
• On the Hardness of Graph Isomorphism
• Beating the generator-enumeration bound for \(p\)-group isomorphism
• Algorithms for group isomorphism via group extensions and cohomology
• The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem
• On the complexity of identifying strongly regular graphs

This page was built for publication: Graph isomorphism is not \(\mathrm{AC}^0\) reducible to group isomorphism

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