# Limitations on hardness vs. randomness under uniform reductions

### Citation:

Gutfreund, Dan, and Salil Vadhan. “Limitations on hardness vs. randomness under uniform reductions.” In Proceedings of the 12th International Workshop on Randomization and Computation (RANDOM ‘08), Lecture Notes in Computer Science, 5171:469-482. Springer-Verlag, 2008.
 RANDOM2008.pdf 443 KB

### Abstract:

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 [10] and Trevisan and Vadhan [24] 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 [10] 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 BPPNP (and thus are unlikely to exist for all of PSPACE).

– Adaptive black-box reductions, with the same restriction on the adaptivity as above, can only exist for functions $${f}$$ in PSPACE (and thus are unlikely to exist for all of EXP).

Beyond shedding light on proof techniques in the area of hardness vs. randomness, our results (together with [10,24]) 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).

Publisher's Version

Last updated on 07/14/2020