On Extractors and Exposure-Resilient Functions for Sublogarithmic Entropy

Yakir Reshef and Salil Vadhan


Abstract

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).


Versions



 [ back to Salil Vadhan's research]