# Limitations of Hardness vs.
Randomness

under Uniform Reductions

Dan Gutfreund and Salil Vadhan

### 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 (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:

*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).
*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 [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).

### Versions

*Electronic Colloquium on Computational Complexity, *Technical
Report TR08-007, February 2008. [pdf][official
ECCC page]
- In
*Proceedings of the* *12th
International Workshop on Randomization and Computation (RANDOM `08),volume* 5171
of* Lecture Notes in Computer Science,
*pages 469-482. Springer-Verlag, 25-27 August 2008. [pdf][Springer page]

[ back to Salil Vadhan's research]