Sparse extractor families for all the entropy
Andrej Bogdanov, Siyao Guo · 2013
We consider the problem of extracting entropy by sparse transformations, namely functions with a small number of overall input-output dependencies. In contrast to previous works, we seek extractors for essentially all the entropy without any assumption on the underlying distribution beyond a min-entropy requirement. We give two simple constructions of sparse extractor families. These are collections of sparse functions such that for any distribution X on inputs of sufficiently high min-entropy, the output of most functions from the collection on input X is statistically close to uniform.