Increasing the output length of zero‐error dispersers
Abstract
Let $\cal{C}$ be a class of probability distributions over a finite set Ω. A function $D : \Omega \mapsto\{0,1\}^{m}$ is a disperser for $\cal{C}$ with entropy threshold $k$ and error $\epsilon$ if for any distribution X in $\cal{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-\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 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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Feb 08, 2011
- Source ID
- 10.1002/rsa.20359
Entities
People
- Ariel Gabizon
- Ronen Shaltiel
Organizations
- Defense Advanced Research Projects Agency
- Israel Science Foundation