2025/06/18 by Cameron Foreman, Lewis Wooltorton, Foreman, Cameron +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Blind Source Separation Techniques #Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Physical sciences #Image Processing Techniques and Applications #Quantum Physics (quant-ph) #Spectroscopy Techniques in Biomedical and Chemical Research
paper · pdf · doi:10.48550/arxiv.2506.15547
openalex publication_date 2025/06/18 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28
Randomness extractors are algorithms that distill weak random sources into near-perfect random numbers. Two-source extractors enable this distillation process by combining two independent weak random sources. Raz's extractor (STOC '05) was the first to achieve this in a setting where one source has linear min-entropy (i.e., proportional to its length), while the other has only logarithmic min-entropy in its length. However, Raz's original construction is impractical due to a polynomial computation time of at least degree 4. Our work solves this problem by presenting an improved version of Raz's extractor with quasi-linear computation time, as well as a new analytic theorem with reduced entropy requirements. We provide comprehensive analytical and numerical comparisons of our construction with others in the literature, and we derive strong and quantum-proof versions of our efficient Raz extractor. Additionally, we offer an easy-to-use, open-source code implementation of the extractor and a numerical parameter calculation module.