loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th Annual IEEE Conference on Computational Complexity (CCC'04)
Solvable Group Isomorphism is (almost) in NP ∩ CoNP
Amherst, Massachusetts
June 21-June 24
ISBN: 0-7695-2120-7
ASCII Text
x 
 
V. Arvind, Jacobo Torán, "Solvable Group Isomorphism is (almost) in NP ∩ CoNP," Computational Complexity, Annual IEEE Conference on, pp. 91-103, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2004.1313808,
author = {V. Arvind and Jacobo Torán},
title = {Solvable Group Isomorphism is (almost) in NP ∩ CoNP},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2004},
issn = {1093-0159},
pages = {91-103},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313808},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Solvable Group Isomorphism is (almost) in NP ∩ CoNP
SN - 1093-0159
SP91
EP103
A1 - V. Arvind,
A1 - Jacobo Torán,
PY - 2004
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
V. Arvind, Institute of Mathematical Sciences
Jacobo Torán, Universität Ulm

The Group Isomorphism problem consists in deciding whether two input groups G_1 and G_2 given by their multiplication tables are isomorphic. We first give a 2-round Arthur-Merlin protocol for the Group Non-Isomorphism problem such that on input groups (G_1,G_2) of size n, Arthur uses O(log^6 n) random bits and Merlin uses O(log^2 n) nondeterministic bits. We derandomize this protocol for the case of solvable groups showing the following two results:

  • (a) We give a uniform NP machine for solvable Group Non-Isomorphism, that works correctly on all but 2^polylog(n) inputs of any length n. Furthermore, this NP machine is always correct when the input groups are nonisomorphic. The NP machine is obtained by an unconditional derandomization of the AM protocol.
  • (b) Under the assumption that EXP ⊈ i.o.PSPACE we get a complete derandomization of the above AM protocol. Thus, EXP ⊈ i.o.PSPACE implies that Group Isomorphism for solvable groups is in NP ∩ coNP.

    • Citation:
    V. Arvind, Jacobo Torán, "Solvable Group Isomorphism is (almost) in NP ∩ CoNP," ccc, pp.91-103, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004
    Usage of this product signifies your acceptance of the Terms of Use.