License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2010.317
URN: urn:nbn:de:0030-drops-28748
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2874/
Go to the corresponding LIPIcs Volume Portal

Chattopadhyay, Arkadev ; Torán, Jacobo ; Wagner, Fabian

Graph Isomorphism is not AC^0 reducible to Group Isomorphism

pdf-format:
28.pdf (0.5 MB)

Abstract

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 \cite{Wolf 94} 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 AC0 reducible to Graph Isomorphism, this implies that Graph Isomorphism is strictly harder than Group or Quasigroup Isomorphism under the ordering defined by AC0 reductions.

BibTeX - Entry

@InProceedings{chattopadhyay_et_al:LIPIcs:2010:2874,
  author =	{Arkadev Chattopadhyay and Jacobo Tor{\'a}n and Fabian Wagner},
  title =	{{Graph Isomorphism is not AC^0 reducible to Group Isomorphism}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{317--326},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Kamal Lodaya and Meena Mahajan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2874},
  URN =		{urn:nbn:de:0030-drops-28748},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.317},
  annote =	{Keywords: Complexity, Algorithms, Group Isomorphism Problem, Circuit Com plexity}
}

Keywords: Complexity, Algorithms, Group Isomorphism Problem, Circuit Com plexity
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Issue Date: 2010
Date of publication: 14.12.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI