Access Restriction

Author Shaltiel, Ronen ♦ Umans, Christopher
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2005
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Hardness versus randomness ♦ Pseudorandom generator ♦ Randomness extractor
Abstract A “randomness extractor” is an algorithm that given a sample from a distribution with sufficiently high min-entropy and a short random seed produces an output that is statistically indistinguishable from uniform. (Min-entropy is a measure of the amount of randomness in a distribution.) We present a simple, self-contained extractor construction that produces good extractors for all min-entropies. Our construction is algebraic and builds on a new polynomial-based approach introduced by Ta-Shma et al. [2001b]. Using our improvements, we obtain, for example, an extractor with output length $\textit{m}$ = $\textit{k}/(log$ $n)^{O(1/α)}$ and seed length (1 + α)log $\textit{n}$ for an arbitrary 0 < α ≤ 1, where $\textit{n}$ is the input length, and $\textit{k}$ is the min-entropy of the input distribution.A “pseudorandom generator” is an algorithm that given a short random seed produces a long output that is computationally indistinguishable from uniform. Our technique also gives a new way to construct pseudorandom generators from functions that require large circuits. Our pseudorandom generator construction is $\textit{not}$ based on the Nisan-Wigderson generator [Nisan and Wigderson 1994], and turns worst-case hardness $\textit{directly}$ into pseudorandomness. The parameters of our generator match those in Impagliazzo and Wigderson [1997] and Sudan et al. [2001] and in particular are strong enough to obtain a new proof that $\textit{P}$ = $\textit{BPP}$ if $\textit{E}$ requires exponential size circuits.Our construction also gives the following improvements over previous work:---We construct an optimal “hitting set generator” that stretches $\textit{O}(log$ $\textit{n})$ random bits into $s^{Ω(1)}$ pseudorandom bits when given a function on log $\textit{n}$ bits that requires circuits of size $\textit{s}.$ This yields a quantitatively optimal hardness versus randomness tradeoff for both $\textit{RP}$ and $\textit{BPP}$ and solves an open problem raised in Impagliazzo et al. [1999].---We give the first construction of pseudorandom generators that fool $\textit{nondeterministic}$ circuits when given a function that requires large nondeterministic circuits. This technique also give a quantitatively optimal hardness versus randomness tradeoff for $\textit{AM}$ and the first hardness amplification result for nondeterministic circuits.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-03-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 52
Issue Number 2
Page Count 45
Starting Page 172
Ending Page 216

Open content in new tab

   Open content in new tab
Source: ACM Digital Library