2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction

DOI10.4007/annals.2012.176.3.3zbMath1256.05146OpenAlexW2160212276MaRDI QIDQ1928613

Anup Rao, Boaz Barak, Ronen Shaltiel, Avi Wigderson

Publication date: 3 January 2013

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4007/annals.2012.176.3.3

zbMATH Keywords

Ramsey graphsextractorsdispersers

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55)

Related Items (19)

Local Correlation Breakers and Applications to Three-Source Extractors and Mergers ⋮ An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy ⋮ Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ A bipartite version of the Erdős–McKay conjecture ⋮ Distinct degrees and homogeneous sets ⋮ Unnamed Item ⋮ Induced Subgraphs With Many Distinct Degrees ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Non-malleable coding against bit-wise and split-state tampering ⋮ Unnamed Item ⋮ An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs ⋮ How to extract useful randomness from unreliable sources ⋮ Unnamed Item ⋮ Explicit two-source extractors and resilient functions ⋮ Proof of a conjecture on induced subgraphs of Ramsey graphs ⋮ Large cliques and independent sets all over the place ⋮ Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs ⋮ Extractors for small zero-fixing sources

Cites Work

• Unnamed Item
• Unnamed Item
• Constructing Ramsey graphs from Boolean function representations
• Generating quasi-random sequences from semi-random sources
• Expanders that beat the eigenvalue bound: Explicit construction and applications
• Intersection theorems with geometric consequences
• On data structures and asymmetric communication complexity
• The Shannon capacity of a union
• A sum-product estimate in finite fields, and applications
• Low rank co-diagonal matrices and Ramsey graphs
• Extractor Codes
• Randomness conductors and constant-degree lossless expanders
• Better extractors for better codes?
• Extractors
• Extractors with weak random seeds
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources
• MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
• Extractors and pseudorandom generators
• Extracting Randomness via Repeated Condensing
• Extracting Randomness Using Few Independent Sources
• Simulating independence
• Extracting all the randomness and reducing the error in Trevisan's extractors

This page was built for publication: 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction