Almost optimal dispersers

Publisher Website
Google Scholar
Abstract
A (K, E) disperser graph G = (VI, V2, E) is a bipartite graph wit.h the property that for any subset A E VI of cardmality K, the neighbors of A cover at least 1 - E fraction of t,he vertices of V2. Such graphs have many applicat.ions in derandomization. Saks, Srinivasan and Zhou presented an explicit construction of (K = 2k, C) disperser graphs G = (V = (2"),W,E) with an almost optimal degree D = poZy(n,C1), for every E > nn(l). We extend t.heir result for any parameter k < n. 1 Int,roduct.ion A disperser is a sparse graph with strong random-like properties. As such, explicit dispersers have numerous applicat.ions in derandomization (many of them appear- ing in the excellent survey paper by Nisan (Nis96)). The quesstion whether explicit constructions of such graphs do esist attracted much research in the last decade (SipSS, Zuc90, Zuc91, NZ93, SZ94, SSZ95, Zuc96). Saks, Srini- vasan and Zhou (SSZ95) showed an almost optimal dis- perser construction for certain parameters. In thii pa- per we show how to extend their work to give explicit constructions for the whole range of parameters.

This publication has 0 references indexed in Scilit: