%0 Journal Article
%J Journal of the ACM (JACM)
%D 1998
%T Explicit OR-dispersers with polylogarithmic degree
%A Saks,Michael
%A Srinivasan, Aravind
%A Zhou,Shiyu
%K derandomization
%K expander graphs
%K explicit constructions
%K hardness of approximation
%K hashing lemmas
%K imperfect sources of randomness
%K measures of information
%K pseudo-random generators
%K randomized computation
%K time-space tradeoffs
%X An (N, M, T)-OR-disperser is a bipartite multigraph G=(V, W, E) with |V| = N, and |W| = M, having the following expansion property: any subset of V having at least T vertices has a neighbor set of size at least M/2. For any pair of constants &xgr;, &lgr;, 1 ≥ &xgr; > &lgr; ≥ 0, any sufficiently large N, and for any T ≥ 2(logN) M ≤ 2(log N)&lgr;, we give an explicit elementary construction of an (N, M, T)-OR-disperser such that the out-degree of any vertex in V is at most polylogarithmic in 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 R > 0, such a source accepts a single request for an 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.
%B Journal of the ACM (JACM)
%V 45
%P 123 - 154
%8 1998/01//
%@ 0004-5411
%G eng
%U http://doi.acm.org/10.1145/273865.273915
%N 1
%R 10.1145/273865.273915