Conference item icon

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:
Publisher copy:
10.4230/LIPIcs.CCC.2017.7

Authors

More by this author
Institution:
University of Oxford
Oxford college:
Magdalen College
Role:
Author


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


Views and Downloads

Views and downloads will return soon






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP