Explicit dispersers with polylog degree
Michael Saks, Aravind Srinivasan, Shiyu Zhou · 1995
An (N, M, 'T)-disperser is a duected bipartite Multigraph G = (V, W,E) with IV[ = N, IW[ = M and all edges directed from V to W, having the following expansion property: any subset of V having at least T vertices has a neighbor set of sise at least M/2.For any pair of constants (, ~, 1 z ~> ~z 0, ~y suffiaently large N, and for any T ~2(106@, M 0, we give the first polynomial-time simulation of RP algorithms using the output of any "minimally randomn 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 probahiity at most 2-R' to any string.It is minimally random in the sense that any weaker source is insufficient to do a blackbox polynomial-time simulation of RP algorithms.Third, we show improvements on the expander construction and the consequent applications given by Wlgderson and Zuck-"The full version of thk work will be available at the DIMACS www site soon (URIJ http:ildirnacs.