Increasing the output length of zero‐error dispersers

Authors:
Publisher website
Google Scholar
Abstract
Let$\cal{C}$ be a class of probability distributions over a finite set Ω. A function$D : \Omega \mapsto\{0,1\}^{m}$ is adisperserfor$\cal{C}$ withentropy threshold$k$ anderror$\epsilon$ if for any distributionXin$\cal{C}$ such thatXgives positive probability to at least$2^{k}$ elements we have that the distribution$D(X)$ gives positive probability to at least$(1-\epsilon)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 maximizemas a function ofk. For several interesting classes of distributions there are explicit constructions in the literature ofzero‐errordispersers with “small” output lengthm.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 by Shaltiel (CCC'06; Proceedings of the 21st Annual IEEE Conference on Computational Complexity, (2006) 46–60.) building on earlier work by Gabizon, Raz and Shaltiel (SIAM J Comput 36 (2006) 1072–1094). Our techniques are different than those of Shaltiel (CCC'06; Proceedings of the 21st Annual IEEE Conference on Computational Complexity (2006) 46–60) 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$\delta >0$ there is a constant$\eta >0$ such that for sufficiently largenthere is a poly‐time computable function$D :\{0,1\}^{n}\times\{0,1\}^{n}\mapsto\{0,1\}^{\eta n}$ such that for every two independent distributions$X_1,X_2$ over$\{0,1\}^{n}$ each with support size at least$2^{\delta n}$ , the output distribution$D(X_1,X_2)$ has full support. This improves the output length of previous constructions by Barak, Kindler, Shaltiel, Sudakov and Wigderson (Proceedings of the 37th Annual ACM Symposium on Theory of Computing (2005) 1–10) and has applications in Ramsey theory and in improved constructions of certain data structures from the work of Fiat and Naor [SIAM J Comput 22 (1993)].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 Rao (unpublished data) and Gabizon and Raz [Combinatorica 28 (2008)] and achieve$m=\Omega(k)$ for bit‐fixing sources and$m=k-o(k)$ for affine sources over polynomial size fields. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011
Funding Information
  • DARPA (HR0011-08-1-0069)
  • Binational US-Israel Science Foundation (2004329)
  • Israel Science Foundation (686/07)

This publication has 31 references indexed in Scilit: