Low-error two-source extractors for polynomial min-entropy

摘要

We construct explicit two-source extractors for n bit sources, requiring n min-entropy and having error 2 ? n , for some constants 0 1 . Previously, constructions for exponentially small error required either min-entropy 0 49 n cite{Bou05} or three sources cite{Li15}. The construction combines somewhere-random condensers based on the Incidence Theorem cite{Zuc06,Li11}, together with recent machinery surrounding non-malleable extractors.