### Explicit OR-dispersers with polylogarithmic degreeExplicit OR-dispersers with polylogarithmic degree

Access Restriction
Subscribed

 Author Saks, Michael ♦ Srinivasan, Aravind ♦ Zhou, Shiyu Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1998 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Derandomization ♦ Expander graphs ♦ Explicit constructions ♦ Hardness of approximation ♦ Hashing lemmas ♦ Imperfect sources of randomness ♦ Measures of information ♦ Pseudo-random generators ♦ Randomized computation ♦ Time-space tradeoffs Abstract An (N, M, T)-OR-disperser is a bipartite multigraph $\textit{G}=(\textit{V,$ W, E) with $|\textit{V}|$ = $\textit{N},$ and $|\textit{W}|$ = $\textit{M},$ having the following expansion property: any subset of $\textit{V}$ having at least $\textit{T}$ vertices has a neighbor set of size at least $\textit{M}/2.$ For any pair of constants &xgr;, λ, 1 ≥ &xgr; > λ ≥ 0, any sufficiently large $\textit{N},$ and for any $\textit{T}$ ≥ $2(log\textit{N})$ $\textit{M}$ ≤ 2(log $\textit{N})λ,$ we give an explicit elementary construction of an (N, M, T)-OR-disperser such that the out-degree of any vertex in $\textit{V}$ is at most polylogarithmic in $\textit{N}.$ Using this with known applications of OR-dispersers yields several results. First, our construction implies that the complexity class Strong-RP defined by Sipser, equals RP. Second, for any fixed &eegr; > 0, we give the first polynomial-time simulation of RP algorithms using the output of any “&eegr;-minimally random” source. For any integral $\textit{R}$ > 0, such a source accepts a single request for an $\textit{R}-bit$ string and generates the string according to a distribution that assigns probability at most 2™R&eegr; to any string. It is minimally random in the sense that any weaker source is insufficient to do a black-box polynomial-time simulation of RP algorithms. 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 1998-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 45 Issue Number 1 Page Count 32 Starting Page 123 Ending Page 154

#### Open content in new tab

Source: ACM Digital Library