Paper Info
Title
Arthur-Merlin games and the problem of isomorphism testing
Abstract
We survey some recent results related to the complexity of isomorphism testing in different algebraic structures. We concentrate on isomorphism problems for finite groups and rings. The complexity of these problems depends not only on the particular underlying algebraic structure, but also on the way the input instances are encoded. As in the case of better studied isomorphism questions, like graph isomorphism, Arthur-Merlin games provide a good tool for proving upper bounds for these problems in terms of complexity classes. We consider questions related to the number of random and nondeterministic bits used in the Arthur-Merlin protocols for isomorphism testing as well as the derandomization of these protocols.
Year
DOI
Venue
2005
10.1007/11494645_61
CiE
Keywords
Field
DocType
particular underlying algebraic structure,graph isomorphism,different algebraic structure,arthur-merlin game,isomorphism testing,arthur-merlin protocol,isomorphism question,complexity class,isomorphism problem,finite group,upper bound
Complexity class,Discrete mathematics,Combinatorics,Maximum common subgraph isomorphism problem,Nondeterministic algorithm,Graph isomorphism,Computer science,Induced subgraph isomorphism problem,Isomorphism,Order isomorphism,Subgraph isomorphism problem
Conference
Volume
ISSN
ISBN
3526
0302-9743
3-540-26179-6
Citations 
PageRank 
References 
0
0.34
9
Authors
1
Name
Order
Citations
PageRank
Jacobo Torán156449.26