Increasing the Output Length of Zero-ErrorDispersers

摘要

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. In this paper we are interested in explicitly constructing zero-error dispersers (that is dispersers with error ε = 0). 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 D : {0, 1}~n × {0,1}~n → {0, 1}~(ηn) such that for any two independent distributions X_1, X_2 over {0,1}~n 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.