On extractors and exposure‐resilient functions for sublogarithmic entropy1. Issue 3 (27th April 2012)

• Record Type: Journal Article
• Authors: Reshef, Yakir; Vadhan, Salil
• Is Part Of: Random structures & algorithms. Volume 42:Issue 3(2013)
• Page Start: 386
• Page End: 401
• Publication Date: 2012-04-27
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20424
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>We study resilient functions and exposure‐resilient functions in the low‐entropy regime. A <italic>resilient function</italic> (a.k.a. deterministic extractor for oblivious bit‐fixing sources) maps any distribution on <italic>n</italic> ‐bit strings in which <italic>k</italic> bits are uniformly random and the rest are fixed into an output distribution that is close to uniform. With <italic>exposure‐resilient functions</italic>, all the input bits are random, but we ask that the output be close to uniform conditioned on any subset of <italic>n</italic> ‐ <italic>k</italic> input bits. In this paper, we focus on the case that <italic>k</italic> is sublogarithmic in <italic>n</italic>.</p> <p>We simplify and improve an explicit construction of resilient functions for <italic>k</italic> sublogarithmic in <italic>n</italic> due to Kamp and Zuckerman (SICOMP 2006), achieving error exponentially small in <italic>k</italic> rather than polynomially small in <italic>k</italic>. Our main result is that when <italic>k</italic> is sublogarithmic in <italic>n</italic>, the short output length of this construction (<italic>O</italic>(log <italic>k</italic>) output bits) is optimal for extractors computable by a large class of space‐bounded streaming algorithms.</p> <p>Next, we show that a random function is a resilient function with high probability if and only if <italic>k</italic> is superlogarithmic in <italic>n</italic>, 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 <italic>k</italic> is as small as a constant (resp. loglog <italic>n</italic>). No explicit exposure‐resilient functions achieving these parameters are known. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013</p> </abstract>