Fall 2015

Graph Automorphism and Circuit Size

Tuesday, Sep. 29, 2015 12:15 pm12:30 pm PDT

Add to Calendar

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.
Office presentation icon Graph Automorphism and Circuit Size510.5 KB