Title: Zero-Fixing Extractors for Sub-Logarithmic Entropy
Speaker: Igor Shinkar, NYU
Date: Wednesday, January 21, 2015 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
An (n,k)-bit-fixing source is a distribution on n bit strings, that is fixed on n-k of the coordinates, and uniform on the remaining k bits. Explicit constructions of extractors for bit-fixing sources by Gabizon, Raz and Shaltiel (SICOMP 2006) and Rao (CCC 2009) extract (1-o(1))k bits for k = polylog(n), almost matching the probabilistic argument. Intriguingly, unlike other well-studied sources of randomness, a result of Kamp and Zuckerman (SICOMP 2006) shows that, for any k some small portion of the entropy in an (n,k)-bit-fixing source can be extracted. Although the extractor does not extract all the entropy, it does extract log(k)/2 bits.
In this work we prove that when the entropy k is small enough compared to n, this exponential entropy-loss is unavoidable, and it is impossible to extract more than log(k)/2 bits from (n,k)-bit-fixing sources. In some sense the remaining entropy is inaccessible, information theoretically.
In fact, our impossibility result holds for what we call zero-fixing sources. These are bit-fixing sources where the fixed bits are set to 0. We complement our negative result, by giving an explicit construction of an (n,k)-zero-fixing extractor, that outputs Omega(k) bits, even for k = polyloglog(n).
Furthermore, we give a construction of an (n,k)-bit-fixing extractor, for entropy k = (1+o(1))loglog(n), with running time n^polyloglog(n). We also give a new construction of an (n,k)-bit-fixing extractor, for entropy k = polylog(n) based on multi-source extractors.
Joint work with Gil Cohen
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S15/