Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs

DOI10.1137/16M1096219MaRDI QIDQ4997309zbMATH OpenWikidataFDO

Authors Gil Cohen

Publication date 29 June 2021

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/16M1096219

zbMATH Keywords

explicit constructionsRamsey graphstwo-source dispersers

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Ramsey theory (05D10) Measures of information, entropy (94A17)

Recommendations

• Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs
• 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
• 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
• Towards optimal two-source extractors and Ramsey graphs
• Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors

Cites work

• 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
• A 2-Source Almost-Extractor for Linear Entropy
• A note on constructive methods for ramsey numbers
• An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Chain Rules for Smooth Min- and Max-Entropies
• Constructing Ramsey graphs from Boolean function representations
• Explicit two-source extractors and resilient functions
• Extracting Randomness Using Few Independent Sources
• Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources
• Extractors with weak random seeds
• From affine to two-source extractors via approximate duality
• scientific article; zbMATH DE number 3458659 (Why is no real title available?)
• scientific article; zbMATH DE number 3616470 (Why is no real title available?)
• scientific article; zbMATH DE number 2196516 (Why is no real title available?)
• Implicit O(1) Probe Search
• Improved non-malleable extractors, non-malleable codes and independent source extractors
• Increasing the Output Length of Zero-Error Dispersers
• Intersection theorems with geometric consequences
• Local correlation breakers and applications to three-source extractors and mergers
• Low rank co-diagonal matrices and Ramsey graphs
• Lower bounds for some Ramsey numbers
• MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
• Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors
• Some remarks on the theory of graphs
• The Shannon capacity of a union
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(7)

• 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
• 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
• On efficient constructions of short lists containing mostly Ramsey graphs
• Ramsey properties of algebraic graphs and hypergraphs
• Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs
• Seed-protecting extractors
• An explicit economical additive basis

This page was built for publication: Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4997309)