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.

Page view(s)

checked on May 26, 2022

Google ScholarTM


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