Reductions to graph isomorphism
type: Item
instance of: scholarly article
title: Reductions to graph isomorphism
zbMATH Open document ID: 1205.68167
published in: Theory of Computing Systems
publication date: 2010-08-13T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5770233
zbMATH Keywords: computational complexity
zbMATH Keywords: reducibilities
zbMATH Keywords: graph isomorphism
author: Jacobo Torán
MaRDI profile type: MaRDI publication profile
full work available at URL: s00224-008-9159-1
OpenAlex ID: W2005365874
cites work: Reductions in circuit complexity: An isomorphism theorem and a gap theorem
cites work: Adaptive logspace reducibility and parallel time
cites work: On uniformity within \(NC^ 1\)
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Group-theoretic algorithms and graph isomorphism
cites work: Completeness results for graph isomorphism.
cites work: Graph isomorphism is low for PP
cites work: Equivalence of NC\(^ k\) and AC\(^{k-1}\) closures of NP and other classes
cites work: On uniform circuit complexity
cites work: Space-bounded hierarchies and probabilistic computations
cites work: Promise problems complete for complexity classes
cites work: On the Hardness of Graph Isomorphism
cites work: On the Decomposability of $NC$ and $AC$
DOI: 10.1007/S00224-008-9159-1
description: scientific article; zbMATH DE number 5770233