Three-Source Extractors for Polylogarithmic Min-Entropy

We continue the study of constructing explicit extractors for independent general weak random sources. The ultimate goal is to give a construction that matches what is given by the probabilistic method - an extractor for two independent n-bit weak random sources with min-entropy as small as log n + O(1). Previously, the best known result in the two-source case is an extractor by Bourgain [1], which works for min-entropy 0.49n; and the best known result in the general case is an earlier work of the author [2], which gives an extractor for a constant number of independent sources with min-entropy polylog(n). However, the constant in the construction of [2] depends on the hidden constant in the best known seeded extractor, and can be large; moreover the error in that construction is only 1/poly(n). In this paper, we make two important improvements over the result in [2]. First, we construct an explicit extractor for three independent sources on n bits with min-entropy k ≥ polylog(n). In fact, our extractor works for one source with poly-logarithmic min-entropy and another independent block source with two blocks each having poly-logarithmic min-entropy. This significantly improves previous constructions, and the next step would be to break the 0.49n barrier in two-source extractors. Second, we improve the error of the extractor from 1/poly(n) to 2^-kΩ(1), which is almost optimal and crucial for cryptographic applications. Some of our techniques may be of independent interests.