Limitations of Hardness vs. Randomness under Uniform Reductions.
Dan Gutfreund, Salil Vadhan · 2008
We consider (uniform) reductions from computing a function f to the task of distinguishing the output of some pseudorandom generator G from uniform. Impagliazzo and Wigderson [IW] and Trevisan and Vadhan [TV] exhibited such reductions for every function f in PSPACE. Moreover, their reductions are “black box,” showing how to use any distinguisher T, given as oracle, in order to compute f (regardless of the complexity of T). The reductions are also adaptive, but only mildly (queries of the same length do not occur in different levels of adaptivity). Impagliazzo and Wigderson [IW] also exhibited such reductions for every function f in EXP, but those reductions are not black-box, because they only work when the oracle T is computable by small circuits. Our main results are that: • Nonadaptive black-box reductions as above can only exist for functions f in BPP NP (and thus are unlikely to exist for all of PSPACE). • Mildly adaptive black-box reductions as above can only exist for functions f in PSPACE (and thus are unlikely to exist for all of EXP).