@article {17595,
	title = {Explicit OR-dispersers with polylogarithmic degree},
	journal = {Journal of the ACM (JACM)},
	volume = {45},
	year = {1998},
	month = {1998/01//},
	pages = {123 - 154},
	abstract = {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 {\textquotedblleft}\&eegr;-minimally random{\textquotedblright} 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.},
	keywords = {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},
	isbn = {0004-5411},
	doi = {10.1145/273865.273915},
	url = {http://doi.acm.org/10.1145/273865.273915},
	author = {Saks,Michael and Srinivasan, Aravind and Zhou,Shiyu}
}
@conference {17577,
	title = {Computing with very weak random sources},
	booktitle = {, 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings},
	year = {1994},
	month = {1994/11/20/22},
	pages = {264 - 275},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {For any fixed ε>0, we show how to simulate RP algorithms in time nO(log n) using the output of a δ-source with min-entropy R(ε). Such a weak random source is asked once for R(ε) bits; it outputs an R-bit string such that any string has probability at most 2-R(ε). If ε>1-1/(k+1), our BPP simulations take time nO(log(k n)) (log(k) is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy RΩ(1), which is optimal. We present applications to time-space tradeoffs, expander constructions, and the hardness of approximation. Also of interest is our randomness-efficient Leftover Hash Lemma, found independently by Goldreich and Wigderson},
	keywords = {Application software, BPP simulations, Chor-Goldreich sources, computational complexity, Computational modeling, Computer science, Computer simulation, cryptography, distributed algorithms, expander constructions, hardness, MATHEMATICS, min-entropy, Physics computing, Polynomials, probability, R-bit string, randomness-efficient Leftover Hash Lemma, RP algorithms simulation, Testing, time-space tradeoffs, very weak random sources},
	isbn = {0-8186-6580-7},
	doi = {10.1109/SFCS.1994.365688},
	author = {Srinivasan, Aravind and Zuckerman,D.}
}
