Yakir Reshef and Salil Vadhan

We study deterministic extractors for bit-fixing sources (a.k.a. resilient functions) and exposure-resilient functions for small min-entropy. That is, of the n bits given as input to the function, k<<n bits are uniformly random and unknown to the adversary.

We show that a random function is a resilient function with high probability if and only if k is at least roughly log n. 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. loglog n).

Next we simplify and improve an explicit construction of resilient functions for sublogarithmic $k$ due to Kamp and Zuckerman (SICOMP 2006), achieving error exponentially small in k rather than polynomially small in k. Finally, we show that the short output length (O(log k)) of this construction must hold for any resilient function computed by a restricted type of space-bounded streaming algorithm (as is the case for our construction).

- Manuscript, March 2010. [arXiv:1003.4029v1][pdf]
- Minor revision, May 2010. [arXiv:1003.4029v2][pdf]
- Minor revision, Nov. 2010. [arXiv:1003.4029v3][pdf]