EXPLICIT OR-DISPERSERS WITH POLYLOGARITHMIC DEGREE

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 su bset of V having at least T vertices has a neighbor set of size at lea st M/2. For any pair of constants xi, lambda, 1 greater than or equal to xi > lambda greater than or equal to 0, any sufficiently large N, a nd for any T greater than or equal to 2((log N)xi), M less than or equ al to 2((log N))(lambda), 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 impl ies that the complexity class Strong-RP defined by Sipser, equals RP. Second, for any fixed eta > 0, we give the first polynomial-time simul ation of RP algorithms using the output of any ''eta-minimally random' ' source. For any integral R > 0, such a source accepts a single reque st for an R-bit string and generates the string according to a distrib ution that assigns probability at most 2(-R eta) to any string. It is minimally random in the sense that any weaker source is insufficient t o do a black-box polynomial-time simulation of RP algorithms.