Extractors with weak random seeds

DOI10.1145/1060590.1060593zbMath1192.68373OpenAlexW1976815826MaRDI QIDQ3581381

Ran Raz

Publication date: 16 August 2010

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Related Items (36)

Improved computational extractors and their applications ⋮ Zero-Fixing Extractors for Sub-Logarithmic Entropy ⋮ From Affine to Two-Source Extractors via Approximate Duality ⋮ Local Correlation Breakers and Applications to Three-Source Extractors and Mergers ⋮ Deterministic extractors for affine sources over large fields ⋮ An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy ⋮ Extracting Computational Entropy and Learning Noisy Linear Functions ⋮ 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction ⋮ Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors ⋮ Analyzing linear mergers ⋮ Extractors: low entropy requirements colliding with non-malleability ⋮ Unnamed Item ⋮ How to get more mileage from randomness extractors ⋮ Nonmalleable Extractors and Codes, with Their Many Tampered Extensions ⋮ Increasing the Output Length of Zero-Error Dispersers ⋮ Deterministic extractors for small-space sources ⋮ Improved Extractors for Recognizable and Algebraic Sources ⋮ An Introduction to Randomness Extractors ⋮ Non-malleable coding against bit-wise and split-state tampering ⋮ Leakage-resilient coin tossing ⋮ Improving the Hadamard extractor ⋮ On Generating Independent Random Strings ⋮ Extracting Kolmogorov complexity with applications to dimension zero-one laws ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Extractors and Lower Bounds for Locally Samplable Sources ⋮ Extracting randomness from extractor-dependent sources ⋮ How to extract useful randomness from unreliable sources ⋮ Low error efficient computational extractors in the CRS model ⋮ Unnamed Item ⋮ Multi-source non-malleable extractors and applications ⋮ Unnamed Item ⋮ Bounds on Fixed Input/Output Length Post-processing Functions for Biased Physical Random Number Generators ⋮ Explicit two-source extractors and resilient functions ⋮ Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs ⋮ Increasing the output length of zero-error dispersers

This page was built for publication: Extractors with weak random seeds