License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2017.7
URN: urn:nbn:de:0030-drops-75406
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7540/
Go to the corresponding LIPIcs Volume Portal

Hirahara, Shuichi ; Santhanam, Rahul

On the Average-Case Complexity of MCSP and Its Variants

pdf-format:
LIPIcs-CCC-2017-7.pdf (0.6 MB)

Abstract

We prove various results on the complexity of MCSP (Minimum Circuit Size Problem) and the related MKTP (Minimum Kolmogorov Time-Bounded Complexity Problem):

* We observe that under standard cryptographic assumptions, MCSP has a pseudorandom self-reduction. This is a new notion we define by relaxing the notion of a random self-reduction to allow queries to be pseudorandom rather than uniformly random. As a consequence we derive a weak form of a worst-case to average-case reduction for (a promise version of) MCSP. Our result also distinguishes MCSP from natural NP-complete problems, which are not known to have worst-case to average-case reductions. Indeed, it is known that strong forms of worst-case to average-case reductions for NP-complete problems collapse the Polynomial Hierarchy.

* We prove the first non-trivial formula size lower bounds for MCSP by showing that MCSP requires nearly quadratic-size De Morgan formulas.

* We show average-case 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 co-nondeterministic 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 average-case hardness of MKTP and MCSP when approaching the question of whether these problems are NP-hard.

BibTeX - Entry

@InProceedings{hirahara_et_al:LIPIcs:2017:7540,
  author =	{Shuichi Hirahara and Rahul Santhanam},
  title =	{{On the Average-Case Complexity of MCSP and Its Variants}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{Ryan O'Donnell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7540},
  URN =		{urn:nbn:de:0030-drops-75406},
  doi =		{10.4230/LIPIcs.CCC.2017.7},
  annote =	{Keywords: minimum circuit size problem, average-case complexity, circuit lower bounds, time-bounded Kolmogorov complexity, hardness}
}

Keywords: minimum circuit size problem, average-case complexity, circuit lower bounds, time-bounded Kolmogorov complexity, hardness
Collection: 32nd Computational Complexity Conference (CCC 2017)
Issue Date: 2017
Date of publication: 01.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI