はてなブックマーク

Revision #5 to TR15-119 | 11th February 2019 20:21 Explicit Two-Source Extractors and Resilient Functions Abstract: We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant~$C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain, required each source to hav