Conference item
On the average-case complexity of MCSP and its variants
- 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 selfreduction to allow queries to be pseudorandom rather than uniformly random. As a consequence we derive a weak form of an average-case to worst case reduction for (a promise version of) MCSP. Our result also distinguishes MCSP from natural NP-complete problems, which are not known to have average-case to worst-case reductions. Indeed, it is known that strong forms of average-case to worst-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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 590.9KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.CCC.2017.7
Authors
+
European Research Council
More from this funder
- Funding agency for:
- Santhanam, R
- Grant:
- FP7/2007-2013/ERC615075
- Publisher:
- Schloss Dagstuhl
- Host title:
- 32nd Computational Complexity Conference (CCC 2017)
- Journal:
- CCC'17 More from this journal
- Volume:
- 79
- Pages:
- 7:1--7:20
- Series:
- Leibniz International Proceedings in Informatics (LIPIcs)
- Publication date:
- 2017-07-21
- Acceptance date:
- 2017-04-19
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959770408
- Keywords:
- Pubs id:
-
pubs:691586
- UUID:
-
uuid:f72a4f06-6e30-4b5f-8afa-1ed016cbce74
- Local pid:
-
pubs:691586
- Source identifiers:
-
691586
- Deposit date:
-
2017-04-28
- ARK identifier:
Terms of use
- Copyright holder:
- Hirahara and Santhanam
- Copyright date:
- 2017
- Notes:
-
Copyright © 2017 Hirahara and Santhanam;
licensed under Creative Commons License CC-BY.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record