Paper Info
Title
Non-Black-Box Worst-Case to Average-Case Reductions within NP
Abstract
There are significant obstacles to establishing an equivalence between the worst-case and average-case hardness of NP: Several results suggest that black-box worst-case to averagecase reductions are not likely to be used for reducing any worstcase problem outside coNP to a distributional NP problem. This paper overcomes the barrier. We present the first nonblack-box worst-case to average-case reduction from a problem outside coNP (unless Random 3SAT is easy for coNP algorithms) to a distributional NP problem. Specifically, we consider the minimum time-bounded Kolmogorov complexity problem (MINKT), and prove that there exists a zero-error randomized polynomial-time algorithm approximating the minimum time bounded Kolmogorov complexity k within an additive error ̅O(√ k) if its average-case version admits an errorless heuris tic polynomial-time algorithm. (The converse direction also holds under a plausible derandomization assumption.) We also show that, given a truth table of size 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> approximating the minimum circuit size within a factor of 2( <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1-ε</sup> jn is in BPP for some constant € > 0 if and only if its average-case version is easy. Based on our results, we propose a research program for excluding Heuristica, i.e., establishing an equivalence between the worst-case and average-case hardness of NP through the lens of MINKT or the Minimum Circuit Size Problem (MCSP).
Year
DOI
Venue
2018
10.1109/FOCS.2018.00032
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
Keywords
DocType
Volume
average case complexity,non-black-box reduction,time-bounded Kolmogorov complexity,minimum circuit size problem
Conference
25
ISSN
ISBN
Citations 
1523-8288
978-1-5386-4231-3
1
PageRank 
References 
Authors
0.35
35
1
Name
Order
Citations
PageRank
Shuichi Hirahara173.48