Extractor Lower Bounds, Revisited

DOI10.4230/lipics.approx/random.2020.1OpenAlexW3082295193MaRDI QIDQ6084344

Maciej Obremski, João L. Ribeiro, Divesh Aggarwal, Siyao Guo, Noah Stephens-Davidowitz

Publication date: 31 October 2023

Full work available at URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.1

zbMATH Keywords

explicit constructionslower boundsrandomness extractors

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Randomness is linear in space
• Explicit two-source extractors and resilient functions
• An improved analysis of linear mergers
• On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
• Kakeya Sets, New Mergers, and Old Extractors
• Analyzing linear mergers
• Extractors
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources
• Non-malleable extractors and codes, with their many tampered extensions
• Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
• New independent source extractors with exponential improvement

This page was built for publication: Extractor Lower Bounds, Revisited