Let C be a class of probability distributions over a finite set Ω. A function D : Ω → {0, 1} m is a disperser for C with entropy threshold k and error if for any distribution X in C 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 (1 − )2 m 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. For several interesting classes of distributions there are explicit constructions in the literature of zero-error dispersers with "small" output length m. In this paper we develop a general technique to improve the output length of zero-error dispersers. 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 [32] building on earlier work by [17]). Our techniques are different than those of [32] and in particular give non-trivial results in the errorless case. Using our approach we construct improved zero-error 2-source dispersers. 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 D : {0, 1} n × {0, 1} n → {0, 1} ηn such that for every two independent distributions X 1 , X 2 over {0, 1} n such that support at least 2 δn elements, 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 [15] . 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 [28, 16] and achieve m = Ω(k) for bit-fixing sources and m = k − o(k) for affine sources over polynomial size fields.
Gabizon and Shaltiel REF constructed a weaker object called a disperser over large fields for affine sources.
Increasing the output length of zero-error dispersers
In RANDOM
Mathematics Computer Science