Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-007 | 6th February 2008 00:00

Limitations of Hardness vs. Randomness under Uniform Reductions

RSS-Feed




TR08-007
Authors: Dan Gutfreund, Salil Vadhan
Publication: 8th February 2008 05:46
Downloads: 3163
Keywords: 


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 only "mildly" (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 has small circuits.

Our main results are that:
1. *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).

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



ISSN 1433-8092 | Imprint