Extractors

DOI10.1145/780542.780630zbMath1192.68859OpenAlexW2120164218MaRDI QIDQ3581258

Omer Reingold, Avi Wigderson, Chi-Jen Lu, Salil P. 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

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

Related Items (22)

Quantified Derandomization: How to Find Water in the Ocean ⋮ Local Correlation Breakers and Applications to Three-Source Extractors and Mergers ⋮ Extracting Computational Entropy and Learning Noisy Linear Functions ⋮ A modular framework for quantum-proof randomness extractors ⋮ On locally decodable codes, self-correctable codes, and \(t\)-private PIR ⋮ 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction ⋮ Analyzing linear mergers ⋮ Interactions of computational complexity theory and mathematics ⋮ How to get more mileage from randomness extractors ⋮ Increasing the Output Length of Zero-Error Dispersers ⋮ Lower bounds for adaptive locally decodable codes ⋮ An Introduction to Randomness Extractors ⋮ Extractor Lower Bounds, Revisited ⋮ Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization ⋮ Extracting Kolmogorov complexity with applications to dimension zero-one laws ⋮ Unnamed Item ⋮ Exponential lower bound for 2-query locally decodable codes via a quantum argument ⋮ How to extract useful randomness from unreliable sources ⋮ On ε‐biased generators in NC⁰ ⋮ Explicit two-source extractors and resilient functions ⋮ An optimal lower bound for 2-query locally decodable linear codes ⋮ Increasing the output length of zero-error dispersers

This page was built for publication: Extractors