Extractors

DOI10.1145/780542.780630zbMath1192.68859MaRDI QIDQ3581258

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

68Q25: Analysis of algorithms and problem complexity

94B60: Other types of codes

65C10: Random number generation in numerical analysis

68W20: Randomized algorithms

Related Items

Extracting Computational Entropy and Learning Noisy Linear Functions, 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, Extracting Kolmogorov complexity with applications to dimension zero-one laws, An optimal lower bound for 2-query locally decodable linear codes, 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction, Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization, An Introduction to Randomness Extractors, Increasing the output length of zero-error dispersers, Analyzing linear mergers, How to get more mileage from randomness extractors, Increasing the Output Length of Zero-Error Dispersers