Improved Constructions of Three Source Extractors
Xin Li · 2011
We study the problem of constructing extractors for independent weak random sources. The probabilistic method shows that there exists an extractor for two independent weak random sources on n bits with only logarithmic min-entropy. However, previously the best known explicit two source extractor only achieves min-entropy 0.499n, and the best known three source extractor only achieves min-entropy n0.9. It is a long standing open problem to construct extractors that work for smaller min-entropy. In this paper we construct an extractor for three independent weak random sources on n bits with min-entropy n1/2+δ, for any constant 01/2+δ, for any constant 0 <; δ <; 1/2. Our constructions mainly use the extractors for some where random sources in and the lossless condenser in.