Almost optimal dispersers
Amnon Ta‐Shma · 1998
A (K; ffl) disperser graph G = (V 1 ; V 2 ; E) is a bipartite graph with the property that for any subset A ` V 1 of cardinality K, the neighbors of A cover at least 1 \\Gamma ffl fraction of the vertices of V 2 . Such graphs have many applications in derandomization. Saks, Srinivasan and Zhou presented an explicit construction of (K = 2 k ; ffl) disperser graphs G = (V = [2 n ]; W;E) with an almost optimal degree D = poly(n; ffl \\Gamma1 ), for every k n\\Omega\\Gamma27 . We extend their result for any parameter k n. 1 Introduction A disperser is a sparse graph with strong random-like properties. As such, explicit dispersers have numerous applications in derandomization (many of them appearing in the excellent survey paper by Nisan [Nis96]). The question whether explicit constructions of such graphs do exist attracted much research in the last decade [Sip88, Zuc90, Zuc91, NZ93, SZ94, SSZ95, Zuc96]. Saks, Srinivasan and Zhou [SSZ95] showed an almost optimal disperser constructio...