@article {634296,
	title = {On extractors and exposure-resilient functions for sublogarithmic entropy},
	journal = {Random Structures \& Algorithms},
	volume = {42},
	number = {3},
	year = {2013},
	pages = {386-401},
	abstract = {
	Version History:\&nbsp;Preliminary version posted as\&nbsp;arXiv:1003.4029\&nbsp;(Dec. 2010).



	We study resilient functions and exposure-resilient functions in the low-entropy regime. A\&nbsp;resilient function\&nbsp;(a.k.a. deterministic extractor for oblivious bit-fixing sources) maps any distribution on\&nbsp;n-bit strings in which k\&nbsp;bits are uniformly random and the rest are fixed into an output distribution that is close to uniform. With\&nbsp;exposure-resilient functions, all the input bits are random, but we ask that the output be close to uniform conditioned on any subset of\&nbsp;n {\textendash}\&nbsp;k\&nbsp;input bits. In this paper, we focus on the case that\&nbsp;k\&nbsp;is sublogarithmic in\&nbsp;n.



	We simplify and improve an explicit construction of resilient functions for\&nbsp;k\&nbsp;sublogarithmic in\&nbsp;n\&nbsp;due to Kamp and Zuckerman (SICOMP 2006), achieving error exponentially small in\&nbsp;krather than polynomially small in\&nbsp;k. Our main result is that when\&nbsp;k\&nbsp;is sublogarithmic in\&nbsp;n, the short output length of this construction (\(O(\log\&nbsp;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\&nbsp;k\&nbsp;is superlogarithmic in\&nbsp;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\&nbsp;k\&nbsp;is as small as a constant (resp. log log\&nbsp;n). No explicit exposure-resilient functions achieving these parameters are known.\&nbsp;



	\&nbsp;

},
	url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20424},
	author = {Yakir Reshef and Salil Vadhan}
}
