From Affine to Two-Source Extractors via Approximate Duality
From MaRDI portal
Publication:3451757
DOI10.1137/12089003XzbMath1330.68219MaRDI QIDQ3451757
Publication date: 18 November 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
discrepancyRamsey graphsextractorspolynomial Freiman-Ruzsa conjectureindependent sourcesapproximate dualitydispersersaffine sources
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
A generalization of a theorem of Rothschild and van Lint ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ An Additive Combinatorics Approach Relating Rank to Communication Complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Near optimal bounds in Freiman's theorem
- A probabilistic technique for finding almost-periods of convolutions
- Affine extractors over prime fields
- On the construction of affine extractors
- A new proof of Szemerédi's theorem for arithmetic progressions of length four
- A statistical theorem of set addition
- On the Bogolyubov-Ruzsa lemma
- Deterministic extractors for affine sources over large fields
- 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
- On a Certain Generalization of the Balog–Szemerédi–Gowers Theorem
- Plünnecke's Inequality
- Extractors with weak random seeds
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- 2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness
- Affine dispersers from subspace polynomials
- New Bounds for Matching Vector Families
- MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
- Dispersers for Affine Sources with Sub-polynomial Entropy
- An Additive Combinatorics Approach Relating Rank to Communication Complexity
- Extracting Randomness Using Few Independent Sources
- Some remarks on the theory of graphs
- Simulating independence
