From affine to two-source extractors via approximate duality
DOI10.1145/1993636.1993661zbMATH Open1288.94030OpenAlexW1970282795MaRDI QIDQ5419087FDOQ5419087
Authors: Noga Zewi, Eli Ben-Sasson 
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
Recommendations
- From affine to two-source extractors via approximate duality
- Affine dispersers from subspace polynomials
- An explicit two-source extractor with min-entropy rate near $4/9$
- Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors
- Extracting Randomness Using Few Independent Sources
discrepancyextractorsRamsey graphspolynomial Freiman-Ruzsa conjectureindependent sourcesapproximate dualitydispersersaffine sources
Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Measures of information, entropy (94A17) Combinatorial probability (60C05) Generalized Ramsey theory (05C55) Ramsey theory (05D10)
Cited In (10)
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- An additive combinatorics approach relating rank to communication complexity
- Title not available (Why is that?)
- Affine dispersers from subspace polynomials
- From affine to two-source extractors via approximate duality
- Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs
- On the structure of the spectrum of small sets
- Title not available (Why is that?)
- An introduction to randomness extractors
- A note on subspace evasive sets
This page was built for publication: From affine to two-source extractors via approximate duality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5419087)
