Let be a class of probability distributions over a finite set Ω. A function is a disperser for with entropy threshold k and error if for any distribution X in such that X gives positive probability to at least 2 k elements we have that the distribution D(X) gives positive probability to at least elements. A long line of research is devoted to giving explicit (that is polynomial time computable) dispersers (and related objects called “extractors”) for various classes of distributions while trying to maximize m as a function of k.
In this paper we are interested in explicitly constructing zero-error dispersers (that is dispersers with error ). For several interesting classes of distributions there are explicit constructions in the literature of zero-error dispersers with “small” output length m and we give improved constructions that achieve “large” output length, namely m = Ω(k).
We achieve this by developing a general technique to improve the output length of zero-error dispersers (namely, to transform a disperser with short output length into one with large output length). This strategy works for several classes of sources and is inspired by a transformation that improves the output length of extractors (which was given in [29] building on earlier work by [15]). Nevertheless, we stress that our techniques are different than those of [29] and in particular give non-trivial results in the errorless case.
Using our approach we construct improved zero-error dispersers for the class of 2-sources. More precisely, we show that for any constant δ> 0 there is a constant η> 0 such that for sufficiently large n there is a poly-time computable function such that for any two independent distributions X 1,X 2 over such that both of them support at least 2 δn elements we get that the output distribution D(X 1,X 2) has full support. This improves the output length of previous constructions by [2] and has applications in Ramsey Theory and in constructing certain data structures [13].
We also use our techniques to give explicit constructions of zero-error dispersers for bit-fixing sources and affine sources over polynomially large fields. These constructions improve the best known explicit constructions due to [26,14] and achieve m = Ω(k) for bit-fixing sources and m = k − o(k) for affine sources.