Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-117 | 22nd July 2010 13:53

Graph Isomorphism is not AC^0 reducible to Group Isomorphism


Authors: Arkadev Chattopadhyay, Jacobo Toran, Fabian Wagner
Publication: 22nd July 2010 18:45
Downloads: 5222


We give a new upper bound for the Group and Quasigroup
Isomorphism problems when the input structures
are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of unbounded fan-in with $O(\log\log n)$ depth and $O(\log^2 n)$ nondeterministic bits, where $n$ is the number of group elements. This improves the existing upper bound from Wolf for the problems. In the previous upper bound the circuits have bounded fan-in but depth
$O(\log^2 n)$ and also $O(\log^2 n)$ nondeterministic bits. We then prove that the kind of circuits from our upper bound cannot compute the Parity function. Since Parity is AC$^0$ reducible to Graph Isomorphism, this implies that Graph Isomorphism is strictly harder
than Group or Quasigroup Isomorphism under
the ordering defined by AC$^0$ reductions.

ISSN 1433-8092 | Imprint