Graph Isomorphism is not AC 0 reducible to Group Isomorphism

DOI10.4230/LIPIcs.FSTTCS.2010.317zbMath1245.68101OpenAlexW2120674923MaRDI QIDQ2908861

Fabian Wagner, Arkadev Chattopadhyay, Jacobo Toran

Publication date: 29 August 2012

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

zbMATH Keywords

complexitygroup isomorphism problemcircuit com plexity

Mathematics Subject Classification ID

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

Related Items (3)

Algorithms for Group Isomorphism via Group Extensions and Cohomology ⋮ On isomorphism testing of groups with normal Hall subgroups ⋮ Beating the generator-enumeration bound for \(p\)-group isomorphism

This page was built for publication: Graph Isomorphism is not AC 0 reducible to Group Isomorphism