DIMACS TR: 96-26
Explicit OR-Dispersers with Polylogarithmic Degree
Authors: Michael Saks, Aravind Srinivasan, Shiyu Zhou
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 $\xi,\lam, 1\ge\xi>\lam\ge 0$,
any sufficiently large $N$, and for any $T\ge 2^{(\log N)^{\xi}}$,
$M \leq 2^{(\log N)^{\lam}}$, 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 $\eta > 0$, we give the first polynomial-time simulation of
RP algorithms using the output of any ``$\eta$-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^\eta}$ 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.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-26.ps.gz
DIMACS Home Page