Extractors

DOI10.1145/780542.780630MaRDI QIDQ3581258zbMATH OpenOpenAlexFDO

Authors Chi-Jen Lu, Omer Reingold, A. Wigderson, Salil Vadhan

Publication date 16 August 2010

Published in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Other types of codes (94B60)

Recommendations

• Extractor Lower Bounds, Revisited
• Extractors for small zero-fixing sources
• scientific article; zbMATH DE number 1543340
• Improved computational extractors and their applications
• scientific article; zbMATH DE number 3917745
• Deterministic extractors for small-space sources
• Deterministic extractors for small-space sources
• Extraction capacity and the optimal order of extraction.
• Optimal deterministic extractors for generalized Santha-Vazirani sources
• Dimension extractors and optimal decompression

Cited in

(33)

• An optimal lower bound for 2-query locally decodable linear codes
• Improving the Hadamard extractor
• 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
• How to extract useful randomness from unreliable sources
• Explicit two-source extractors and resilient functions
• A modular framework for quantum-proof randomness extractors
• Lossless condensers, unbalanced expanders, and extractors
• An introduction to randomness extractors
• Increasing the output length of zero-error dispersers
• Local correlation breakers and applications to three-source extractors and mergers
• Extractors and pseudo-random generators with optimal seed length
• Analyzing linear mergers
• How to get more mileage from randomness extractors
• Increasing the Output Length of Zero-Error Dispersers
• Extractors for Three Uneven-Length Sources
• scientific article; zbMATH DE number 3917745 (Why is no real title available?)
• scientific article; zbMATH DE number 1256744 (Why is no real title available?)
• scientific article; zbMATH DE number 1543340 (Why is no real title available?)
• Quantified Derandomization: How to Find Water in the Ocean
• Non-malleable extractors and non-malleable codes: partially optimal constructions
• Extracting Computational Entropy and Learning Noisy Linear Functions
• Simpler Constant-Seed Condensers
• On ε‐biased generators in NC⁰
• Lower bounds for adaptive locally decodable codes
• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• On locally decodable codes, self-correctable codes, and \(t\)-private PIR
• Extractor Lower Bounds, Revisited
• Interactions of computational complexity theory and mathematics
• Almost Chor-Goldreich sources and adversarial random walks
• Seed-protecting extractors
• Two-source and affine non-malleable extractors for small entropy
• Randomness extractors in AC^0 and NC^1: optimal up to constant factors
• Extracting Kolmogorov complexity with applications to dimension zero-one laws

This page was built for publication: Extractors

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