Show simple item record

dc.contributor.authorTrevisan, Luca
dc.contributor.authorVadhan, Salil
dc.date.accessioned2009-05-12T14:17:51Z
dc.date.issued2007
dc.identifier.citationTrevisan, Luca and Salil Vadhan. 2007. Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity, 16, no. 4: 331-364.en
dc.identifier.issn1016-3328en
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:2920115
dc.description.abstractImpagliazzo 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.sponsorshipEngineering and Applied Sciencesen
dc.language.isoen_USen
dc.publisherSpringer Verlagen
dc.relation.isversionofhttp://dx.doi.org/10.1007/s00037-007-0233-xen
dash.licenseLAA
dc.subjectinstance checkersen
dc.subjectaverage-case complexityen
dc.subjectpseudorandomnessen
dc.titlePseudorandomness and Average-Case Complexity via Uniform Reductionsen
dc.relation.journalComputational Complexityen
dash.depositing.authorVadhan, Salil
dc.identifier.doi10.1007/s00037-007-0233-x*
dash.contributor.affiliatedVadhan, Salil


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record