Pseudorandomness and Average-Case Complexity via Uniform Reductions

DSpace/Manakin Repository

Pseudorandomness and Average-Case Complexity via Uniform Reductions

Show simple item record Trevisan, Luca Vadhan, Salil 2009-05-12T14:17:51Z 2007
dc.identifier.citation Trevisan, Luca and Salil Vadhan. 2007. Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity, 16, no. 4: 331-364. en
dc.identifier.issn 1016-3328 en
dc.description.abstract Impagliazzo and Wigderson (36th FOCS, 1998) gave the first construction of pseudorandom generators from a <i>uniform</i> complexity assumption on EXP (namely EXP [not equal to] 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: 1. We obtain an optimal worst-case to average-case connection for EXP: if EXP is not a subset of BPTIME(t(n)), EXP has problems that cannot be solved on a fraction 1/2 +1/t'(n) of the inputs by BPTIME(t'(n)) algorithms, for t'=t^{\Omega(1)}. 2. We exhibit a PSPACE-complete self-correctible and downward self-reducible problem. This slightly simplifies and strengthens the proof of Impaglaizzo and Wigderson, which used a a #P-complete problem with these properties. 3. We argue that the results of Impagliazzo and Wigderson, and the ones in this paper, cannot be proved via "black-box" uniform reductions. en
dc.description.sponsorship Engineering and Applied Sciences en
dc.language.iso en_US en
dc.publisher Springer Verlag en
dc.relation.isversionof en
dash.license LAA
dc.subject instance checkers en
dc.subject average-case complexity en
dc.subject pseudorandomness en
dc.title Pseudorandomness and Average-Case Complexity via Uniform Reductions en
dc.relation.journal Computational Complexity en Vadhan, Salil

Files in this item

Files Size Format View
Vadhan_PsuedorandComplexReduction.pdf 298.0Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record


Search DASH

Advanced Search