Premium
On extractors and exposure‐resilient functions for sublogarithmic entropy
Author(s) -
Reshef Yakir,
Vadhan Salil
Publication year - 2013
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20424
Subject(s) - bounded function , mathematics , binary logarithm , function (biology) , discrete mathematics , entropy (arrow of time) , computable function , combinatorics , physics , mathematical analysis , quantum mechanics , evolutionary biology , biology
We study resilient functions and exposure‐resilient functions in the low‐entropy regime. A resilient function (a.k.a. deterministic extractor for oblivious bit‐fixing sources) maps any distribution on n ‐bit strings in which k bits are uniformly random and the rest are fixed 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 (log k ) 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. loglog n ). No explicit exposure‐resilient functions achieving these parameters are known. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013