Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ISOMORPHISM PROBLEMS:
Reports tagged with Isomorphism problems:
TR10-117 | 22nd July 2010

#### Graph Isomorphism is not AC^0 reducible to Group Isomorphism

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, ... more >>>

TR17-158 | 23rd October 2017
Eric Allender, Joshua Grochow, Dieter van Melkebeek, Cris Moore, Andrew Morgan

#### Minimum Circuit Size, Graph Isomorphism, and Related Problems

We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted as MKTP where circuit size is replaced by a polynomially-related Kolmogorov measure. All prior reductions ... more >>>

ISSN 1433-8092 | Imprint