Extractors for small zero-fixing sources

摘要

A random variable X is an ( n k ) -zero-fixing source if for some subset V [ n ] , X is the uniform distribution on the strings 0 1 n that are zero on every coordinate outside of V . An -extractor for ( n k ) -zero-fixing sources is a mapping F : 0 1 n 0 1 m , for some m , such that F ( X ) is -close in statistical distance to the uniform distribution on 0 1 m for every ( n k ) -zero-fixing source X . Zero-fixing sources were introduced by Cohen and Shinkar in~2015 in connection with the previously studied extractors for bit-fixing sources. They constructed, for every 0" 0 , an efficiently computable extractor that extracts a positive fraction of entropy, i.e., ( k ) bits, from ( n k ) -zero-fixing sources where k ( log log n ) 2+ . In this paper we present two different constructions of extractors for zero-fixing sources that are able to extract a positive fraction of entropy for k essentially smaller than log log n . The first extractor works for k C log log log n , for some constant C . The second extractor extracts a positive fraction of entropy for k log ( i ) n for any fixed i N , where log ( i ) denotes i -times iterated logarithm. The fraction of extracted entropy decreases with i . The first extractor is a function computable in polynomial time in~ n (for = o (1) , but not too small); the second one is computable in polynomial time when k log log n log log log n , where is a positive constant.