Browsing FAS Scholarly Articles by Keyword "pseudorandomness"
Now showing items 1-3 of 3
-
Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions
(ACM Press, 2012)We provide a characterization of pseudoentropy in terms of hardness of sampling: Let (X,B) be jointly distributed random variables such that B takes values in a polynomial-sized set. We show that B is computationally ... -
On Extractors and Exposure-Resilient Functions for Sublogarithmic Entropy
(Wiley-Blackwell, 2013)We study resilient functions and exposure-resilient functions in the low-entropy regime. A resilient function (a.k.a. deterministic extractor for oblivious bit-fixing sources) maps any distribution on n -bit strings in ... -
Pseudorandomness and Average-Case Complexity via Uniform Reductions
(Springer Verlag, 2007)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, ...