2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction

DOI10.1145/1132516.1132611zbMath1301.68191OpenAlexW2135963330MaRDI QIDQ2931427

Avi Wigderson, Anup Rao, Ronen Shaltiel, Boaz Barak

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

Ramsey graphsextractorsindependent sourcesdispersers

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Generalized Ramsey theory (05C55) Measures of information, entropy (94A17) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (21)

From Affine to Two-Source Extractors via Approximate Duality ⋮ Affine extractors over large fields with exponential error ⋮ Some recent results on Ramsey-type numbers ⋮ Extractors for varieties ⋮ Constructing Ramsey graphs from Boolean function representations ⋮ Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors ⋮ Harnessing the Bethe free energy ⋮ Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error ⋮ The size Ramsey number of a directed path ⋮ How to get more mileage from randomness extractors ⋮ Quasi chain rule for min-entropy ⋮ Increasing the Output Length of Zero-Error Dispersers ⋮ An Introduction to Randomness Extractors ⋮ Induced Ramsey-type theorems ⋮ Improving the Hadamard extractor ⋮ The complexity of explicit constructions ⋮ Unnamed Item ⋮ Extractors and Lower Bounds for Locally Samplable Sources ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ Increasing the output length of zero-error dispersers ⋮ Unnamed Item

This page was built for publication: 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction