From affine to two-source extractors via approximate duality

DOI10.1145/1993636.1993661zbMath1288.94030OpenAlexW1970282795MaRDI QIDQ5419087

Eli Ben-Sasson, Noga Zewi

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1993636.1993661

zbMATH Keywords

discrepancyRamsey graphsextractorspolynomial Freiman-Ruzsa conjectureindependent sourcesapproximate dualitydispersersaffine sources

Mathematics Subject Classification ID

Combinatorial probability (60C05) Generalized Ramsey theory (05C55) Measures of information, entropy (94A17) Ramsey theory (05D10) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (7)

Unnamed Item ⋮ On the structure of the spectrum of small sets ⋮ An Introduction to Randomness Extractors ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs ⋮ An Additive Combinatorics Approach Relating Rank to Communication Complexity ⋮ Unnamed Item

This page was built for publication: From affine to two-source extractors via approximate duality