SCIENCE@home

On extractors and exposure-resilient functions for sublogarithmic entropy

Yakir A. Reshef,S. Vadhan

Published 2010 in Random Struct. Algorithms

ABSTRACT

We study resilient functions and exposure-resilient functions in the low-entropy regime. A resilient function (a.k.a. deterministic extractor for oblivious bit-xing sources) maps any distribution on n-bit strings in which k bits are uniformly random and the rest are xed into an output distribution that is close to uniform. With exposure-resilient functions, all the input bits are random, but we ask that the output be close to uniform conditioned on any subset of n k input bits. In this paper, we focus on the case that k is sublogarithmic in n. We simplify and improve an explicit construction of resilient functions for k sublogarithmic in n due to Kamp and Zuckerman (SICOMP 2006), achieving error exponentially small in k rather than polynomially small in k. Our main result is that when k is sublogarithmic in n, the short output length of this construction (O(logk) output bits) is optimal for extractors computable by a large class of space-bounded streaming algorithms. Next, we show that a random function is a resilient function with high probability if and only if k is superlogarithmic in n, suggesting that our main result may apply more generally. In contrast, we show that a random function is a static (resp. adaptive) exposure-resilient function with high probability even if k is as small as a constant (resp. log logn). No explicit exposure-resilient functions achieving these parameters are known.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-18 of 18 references · Page 1 of 1

CITED BY