Abstract
We prove various results on the complexity of MCSP (Minimum Circuit Size Problem) and the related MKTP (Minimum Kolmogorov TimeBounded Complexity Problem):
* We observe that under standard cryptographic assumptions, MCSP has a pseudorandom selfreduction. This is a new notion we define by relaxing the notion of a random selfreduction to allow queries to be pseudorandom rather than uniformly random. As a consequence we derive a weak form of a worstcase to averagecase reduction for (a promise version of) MCSP. Our result also distinguishes MCSP from natural NPcomplete problems, which are not known to have worstcase to averagecase reductions. Indeed, it is known that strong forms of worstcase to averagecase reductions for NPcomplete problems collapse the Polynomial Hierarchy.
* We prove the first nontrivial formula size lower bounds for MCSP by showing that MCSP requires nearly quadraticsize De Morgan formulas.
* We show averagecase superpolynomial size lower bounds for MKTP against AC0[p] for any prime p.
* We show the hardness of MKTP on average under assumptions that have been used in much recent work, such as Feige's assumptions, Alekhnovich's assumption and the Planted Clique conjecture. In addition, MCSP is hard under Alekhnovich's assumption. Using a version of Feige's assumption against conondeterministic algorithms that has been conjectured recently, we provide evidence for the first time that MKTP is not in coNP. Our results suggest that it might worthwhile to focus on the averagecase hardness of MKTP and MCSP when approaching the question of whether these problems are NPhard.
BibTeX  Entry
@InProceedings{hirahara_et_al:LIPIcs:2017:7540,
author = {Shuichi Hirahara and Rahul Santhanam},
title = {{On the AverageCase Complexity of MCSP and Its Variants}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {7:17:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7540},
URN = {urn:nbn:de:0030drops75406},
doi = {10.4230/LIPIcs.CCC.2017.7},
annote = {Keywords: minimum circuit size problem, averagecase complexity, circuit lower bounds, timebounded Kolmogorov complexity, hardness}
}
Keywords: 

minimum circuit size problem, averagecase complexity, circuit lower bounds, timebounded Kolmogorov complexity, hardness 
Collection: 

32nd Computational Complexity Conference (CCC 2017) 
Issue Date: 

2017 
Date of publication: 

01.08.2017 