Improving the Hadamard extractor

In this paper we construct a strong randomness extractor with two independent ℓ-bit input distributions with min entropies bX,bY,bX+bY>ℓ (the probability of any particular output is upper bounded by 2−bX and 2−bY, respectively). For bX,bY≤ℓ−1, our extractor produces one bit which is by the factor of closer to the uniform distribution, when compared to the Hadamard extractor. What is more, this distance drops to zero if at least one of the min entropies raises to ℓ. This is in sharp contrast to the Hadamard extractor which fails to produce even a single unbiased bit, even if one of the input distributions is uniform. We also extend our construction to produce k bits of output with a bias that is by the factor of smaller than that of the corresponding Hadamard extractor and retains the ability to produce unbiased bits if one of the input distributions is uniform. The strongness property of the extractor is maintained in both cases, however, in the multi-bit scenario the bias is increased by the factor of .