Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Isomorphism problems:
TR10-117 | 22nd July 2010
Arkadev Chattopadhyay, Jacobo Toran, Fabian Wagner

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