Unexpected hardness results for Kolmogorov complexity under uniform reductions

Hardness of computing the Kolmogorov complexity of a given string is closely tied to a security proof of hitting set generators, and thus understanding hardness of Kolmogorov complexity is one of the central questions in complexity theory. In this paper, we develop new proof techniques for showing hardness of computing Kolmogorov complexity under surprisingly efficient reductions, which were previously conjectured to be impossible. It is known that the set R K of Kolmogorov-random strings is PSPACE-hard under polynomial-time Turing reductions, i.e., PSPACE ⊂ P R K , and that NEXP ⊂ NP R K , which was conjectured to be tight by Allender (CiE 2012). We prove that EXP NP ⊂ P R K , which simultaneously improves these hardness results and refutes the conjecture of Allender under the plausible assumption that EXP NP ≠ NEXP. At the core of our results is a new security proof of a pseudorandom generator via a black-box uniform reduction, which overcomes an impossibility result of Gutfreund and Vadhan (RANDOM/APPROX 2008).