Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-071 | 1st August 2007 00:00

Reductions to Graph Isomorphism

RSS-Feed




TR07-071
Authors: Jacobo Toran
Publication: 1st August 2007 17:37
Downloads: 1442
Keywords: 


Abstract:

We show that several reducibility notions coincide when applied to the
Graph Isomorphism (GI) problem. In particular we show that if a set is
many-one logspace reducible to GI, then it is in fact many-one AC^0
reducible to GI. For the case of Turing reducibilities we show that for
any k\geq 0 an NC^{k+1} reduction to GI can be transformed into an AC^k
reduction to the same problem.



ISSN 1433-8092 | Imprint