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)
discrepancy; Ramsey graphs; extractors; polynomial Freiman-Ruzsa conjecture; independent sources; approximate duality; dispersers; affine sources
60C05: Combinatorial probability
05C55: Generalized Ramsey theory
94A17: Measures of information, entropy
05D10: Ramsey theory
68W20: Randomized algorithms
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
An Additive Combinatorics Approach Relating Rank to Communication Complexity, A generalization of a theorem of Rothschild and van Lint, A generalization of a theorem of Rothschild and van Lint
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
