Extracting all the Randomness from a Weakly Random Source
Salil Vadhan · DSpace@MIT (Massachusetts Institute of Technology) · 1998
In this paper, we give explicit constructions of extractors which work for a source of any min-entropy on strings of length n. The first construction extracts any constant fraction of the min-entropy using O(log 2 n) additional random bits. The second extracts all the min-entropy using O(log 3 n) additional random bits. Both of these constructions use fewer truly random bits than any previous construction which works for all min-entropies and extracts a constant fraction of the min-entropy. We then improve our second construction and show that we can reduce the entropy loss to 2 log(1=") + O(1) bits, while still using O(log 3 n) truly random bits (where entropy loss is defined as [(source min-entropy) + (# truly random bits used) \\Gamma (# output bits)], and " is the statistical difference from uniform achieved). This entropy loss is optimal up to a constant additive term. These extractors are obtained by observing that a weaker notion of "combinatorial design" suffices for the ...