Limitations of Hardness vs. Randomness
under Uniform Reductions

Dan Gutfreund and Salil Vadhan


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 (FOCS `98, JCSS `01) and Trevisan and Vadhan (CCC `02, CC `07) 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 with the restriction that queries of the same length do not occur in different levels of

adaptivity.  Impagliazzo and Wigderson 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:


Beyond shedding light on proof techniques in the area of hardness vs. randomness, our results (together with [IW,TV]) can be viewed in a more general context as identifying techniques that overcome limitations of black-box reductions, which may be useful elsewhere in complexity theory (and the foundations of cryptography).


 [ back to Salil Vadhan's research]