Please use this identifier to cite or link to this item:
Title: Explicit OR-dispersers with polylogarithmic degree
Authors: Saks, M.
Srinivasan, A. 
Zhou, S.
Keywords: Algorithms
F.1.3 [Computaion by Abstract Devices]: Complexity Classes - relations among randomized complexity classes
G.2.1 [Discrete Mathematics]: Combinatorics - combinatorial algorithms
G.3 [Probability and Statistics]: probabilistic algorithms
Issue Date: Jan-1998
Citation: Saks, M.,Srinivasan, A.,Zhou, S. (1998-01). Explicit OR-dispersers with polylogarithmic degree. Journal of the ACM 45 (1) : 123-154. ScholarBank@NUS Repository.
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.
Source Title: Journal of the ACM
ISSN: 00045411
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.