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.