Explicit OR-dispersers with polylogarithmic degree

Publisher Website
Google Scholar
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 ξ, λ, 1 ≥ ξ > λ ≥ 0, any sufficiently large N , and for any T ≥ 2 (log N ) M ≤ 2 (log N ) λ , 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 η > 0, we give the first polynomial-time simulation of RP algorithms using the output of any “η-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 η 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.