Computer Science – Computational Complexity
Scientific paper
2010-03-21
Computer Science
Computational Complexity
Scientific paper
We study deterministic extractors for oblivious bit-fixing sources (a.k.a. resilient functions) and exposure-resilient functions with small min-entropy: of the function's n input bits, k << n bits are uniformly random and unknown to the adversary. We simplify and improve an explicit construction of extractors for bit-fixing sources with sublogarithmic k 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 an extractor for oblivious bit-fixing sources 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. log log n). No explicit exposure-resilient functions achieving these parameters are known.
Reshef Yakir
Vadhan Salil
No associations
LandOfFree
On Extractors and Exposure-Resilient Functions for Sublogarithmic Entropy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Extractors and Exposure-Resilient Functions for Sublogarithmic Entropy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Extractors and Exposure-Resilient Functions for Sublogarithmic Entropy will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-205848