Minimum Circuit Size, Graph Isomorphism, and Related Problems
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan
Abstract
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 from supposedly-intractable problems to MCSP / MKTP hinged on the power of MCSP / MKTP to distinguish random distributions from distributions produced by hardness-based pseudorandom generator constructions. We develop a fundamentally different approach inspired by the well-known interactive proof system for the complement of Graph Isomorphism (GI). It yields a randomized reduction with zero-sided error from GI to MKTP. We generalize the result and show that GI can be replaced by any isomorphism problem for which the underlying group satisfies some elementary properties. Instantiations include Linear Code Equivalence, Permutation Group Conjugacy, and Matrix Subspace Conjugacy. Along the way we develop encodings of isomorphism classes that are efficiently decodable and achieve compression that is at or near the information-theoretic optimum; those encodings may be of independent interest.
Appearances
Slides
- Talk at Simons Institute MCSP reading group, 2018 Nov 01. slides sources
Figure accompanying slide 17: fig
Notes
This work subsumes and significantly strengthens the earlier technical report ECCC TR15-162 (unrevised version). See our note in ECCC TR17-158 for details on the precise relationship between our work and theirs.
Over the course of strengthening ECCC TR15-162, a so-called smart reduction from Graph Automorphism to Rigid Graph Isomorphism was discovered. It did not find a place in the present work; nevertheless, an exposition can be found in ECCC TR15-162 (revised version) (pdf).
Errata
In section 7.1 (SICOMP version) we discuss extending our work to MCSP. We cite [43] as a lower bound on the circuit complexity of a random function; however, [43] turns out to be flawed (cf. the work of Lozhkin and Shiganov (ECCC TR11-130)). Instead, one may replace the value “2” by “1” in the setting of κ(s,t), and then (7.1) follows from [18]. Section 7.1 otherwise remains in tact.