Allender, Eric ;
Grochow, Joshua A. ;
van Melkebeek, Dieter ;
Moore, Cristopher ;
Morgan, Andrew
Minimum Circuit Size, Graph Isomorphism, and Related Problems
Abstract
We study the computational power of deciding whether a given truthtable can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted MKTP where circuit size is replaced by a polynomiallyrelated Kolmogorov measure. All prior reductions from supposedlyintractable problems to MCSP / MKTP hinged on the power of MCSP / MKTP to distinguish random distributions from distributions produced by hardnessbased pseudorandom generator constructions. We develop a fundamentally different approach inspired by the wellknown interactive proof system for the complement of Graph Isomorphism (GI). It yields a randomized reduction with zerosided 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 informationtheoretic optimum; those encodings may be of independent interest.
BibTeX  Entry
@InProceedings{allender_et_al:LIPIcs:2018:8345,
author = {Eric Allender and Joshua A. Grochow and Dieter van Melkebeek and Cristopher Moore and Andrew Morgan},
title = {{Minimum Circuit Size, Graph Isomorphism, and Related Problems}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {20:120:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770606},
ISSN = {18688969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8345},
URN = {urn:nbn:de:0030drops83455},
doi = {10.4230/LIPIcs.ITCS.2018.20},
annote = {Keywords: Reductions between NPintermediate problems, Graph Isomorphism, Minimum Circuit Size Problem, timebounded Kolmogorov complexity}
}
2018
Keywords: 

Reductions between NPintermediate problems, Graph Isomorphism, Minimum Circuit Size Problem, timebounded Kolmogorov complexity 
Seminar: 

9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Issue date: 

2018 
Date of publication: 

2018 