On extractors and exposure‐resilient functions for sublogarithmic entropy
Yakir Reshef, Salil Vadhan · Random Structures and Algorithms · 2012
Abstract We study resilient functions and exposure‐resilient functions in the low‐entropy regime. Aresilient function(a.k.a. deterministic extractor for oblivious bit‐fixing sources) maps any distribution onn‐bit strings in whichkbits are uniformly random and the rest are fixed into an output distribution that is close to uniform. Withexposure‐resilient functions, all the input bits are random, but we ask that the output be close to uniform conditioned on any subset ofn‐kinput bits. In this paper, we focus on the case thatkis sublogarithmic inn. We simplify and improve an explicit construction of resilient functions forksublogarithmic inndue to Kamp and Zuckerman (SICOMP 2006), achieving error exponentially small inkrather than polynomially small ink. Our main result is that whenkis sublogarithmic inn, 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 ifkis superlogarithmic inn, 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 ifkis as small as a constant (resp. loglogn). No explicit exposure‐resilient functions achieving these parameters are known. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013