Abstract
A long-standing open problem in the theory of average-case complexity is to establish a connection from worst-case hardness of NP to average-case hardness of NP. Standard proof techniques, such as (nonadaptive black-box) reductions, hardness amplification procedures, and relativizing proof techniques are known to be insufficient to resolve this open problem. In this talk, I will present a new proof technique that overcomes the limits of black-box reductions and hardness amplification procedures (but not relativizing proof techniques). The proof technique is based on meta-complexity of time-bounded Kolmogorov complexity.