# zbMATH — the first resource for mathematics

Pseudorandomness and average-case complexity via uniform reductions. (English) Zbl 1133.68023
Summary: R. Impagliazzo and A. Wigderson [J. Comput. Syst. Sci. 63, No. 4, 672–688 (2001; Zbl 1052.68034)] gave the first construction of pseudorandom generators from a uniform complexity assumption on EXP (namely EXP $$\not=$$ BPP). Unlike results in the nonuniform setting, their result does not provide a continuous trade-off between worst-case hardness and pseudorandomness, nor does it explicitly establish an average-case hardness result. In this paper: We obtain an optimal worst-case to average-case connection for EXP: if EXP $$\nsubseteq$$ BPTIME($$t (n)$$), then EXP has problems that cannot be solved on a fraction $$1/2 + 1/t^{\prime}(n)$$ of the inputs by BPTIME $$(t^{\prime}(n))$$ algorithms, for $$t^{\prime}= t^{\Omega(1)}$$. We exhibit a PSPACE-complete self-correctible and downward self-reducible problem. This slightly simplifies and strengthens the proof of Impagliazzo and Wigderson, which used a #P-complete problem with these properties. We argue that the results of Impagliazzo and Wigderson, and the ones in this paper, cannot be proved via “black-box” uniform reductions.

##### MSC:
 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Full Text: