Abstract
The Minimum Circuit Size Problem is a well-studied example of a problem in NP that is believed to be intractable, but is not widely believed to be NP-complete. Until now, all reductions from of seemingly-hard problems to MCSP have made use of the [HILL] pseudorandom generator, which shows that any polynomial-time computable function can be inverted with relatively high probability by a probabilistic oracle machine with access to MCSP. This approach is not suitable for presenting a ZPP-reduction to MCSP from a problem that is not known to be in NP intersect coNP.
Our main contribution is to present a very different reduction from Graph Isomorphism to MCSP; the reduction does not make use of [HILL]. (The reduction does require some new graph-theoreticl algorithms.) We use this to show that the Graph Automorphism problem is in ZPP relative to MCSP.
This is joint work with Josh Grochow and Cris Moore.