Improved Constructions of Two-Source Extractors

2015/08/05 by Xin Li, Li, Xin
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC

paper · pdf · doi:10.48550/arxiv.1508.01115

arxiv created 2015/08/05 · arxiv updated 2015/08/06

Abstract

In a recent breakthrough \citeCZ15, Chattopadhyay and Zuckerman gave an explicit two-source extractor for min-entropy k ≥ log^C n for some large enough constant C. However, their extractor only outputs one bit. In this paper, we improve the output of the two-source extractor to k^Ω(1), while the error remains n^-Ω(1). Our improvement is obtained by giving a better extractor for (q, t, γ) non-oblivious bit-fixing sources, which can output t^Ω(1) bits instead of one bit as in \citeCZ15.

Related

• Three-Source Extractors for Polylogarithmic Min-Entropy
• Two-Source and Affine Non-Malleable Extractors for Small Entropy
• Extractors: Low Entropy Requirements Colliding With Non-Malleability
• Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification
• Improved Extractors for Small-Space Sources