DIMACS TR: 96-26

Explicit OR-Dispersers with Polylogarithmic Degree

Authors: Michael Saks, Aravind Srinivasan, Shiyu Zhou


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