Improved Extractors for Recognizable and Algebraic Sources

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.72OpenAlexW2981179935MaRDI QIDQ5875532

Fu Li, David Zuckerman

Publication date: 3 February 2023

Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2019/11287/pdf/LIPIcs-APPROX-RANDOM-2019-72.pdf

zbMATH Keywords

pseudorandomnessextractor

Mathematics Subject Classification ID

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

Related Items

(Nondeterministic) hardness vs. non-malleability, How to extract useful randomness from unreliable sources

Cites Work

• Unnamed Item
• Unnamed Item
• Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• Weak derandomization of weak algorithms: explicit versions of Yao's lemma
• Extractors and rank extractors for polynomial sources
• On the construction of affine extractors
• Generating quasi-random sequences from semi-random sources
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Randomness is linear in space
• Extractors for varieties
• Weighted Gate Elimination
• Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
• Three XOR-Lemmas — An Exposition
• Extractors with weak random seeds
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Class of constructive asymptotically good algebraic codes
• Hard Functions for Low-Degree Polynomials over Prime Fields
• Deterministic extractors for small-space sources