Extractors from Reed-Muller codes
From MaRDI portal
Publication:2496317
DOI10.1016/j.jcss.2005.05.010zbMath1094.68036OpenAlexW1556285486WikidataQ62398473 ScholiaQ62398473MaRDI QIDQ2496317
David Zuckerman, Amnon Ta-Shma, Shmuel Safra
Publication date: 12 July 2006
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2005.05.010
Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Algorithms in computer science (68W99)
Related Items
On the complexity of approximating the VC dimension. ⋮ Robustly reusable fuzzy extractor with imperfect randomness ⋮ Deterministic extractors for affine sources over large fields ⋮ Reconstructive dispersers and hitting set generators ⋮ A modular framework for quantum-proof randomness extractors ⋮ Unnamed Item ⋮ Local List Recovery of High-Rate Tensor Codes and Applications ⋮ Unnamed Item ⋮ An Introduction to Randomness Extractors ⋮ Simple extractors via constructions of cryptographic pseudo-random generators ⋮ Extracting Kolmogorov complexity with applications to dimension zero-one laws ⋮ Pseudo-random generators for all hardnesses ⋮ Another Motivation for Reducing the Randomness Complexity of Algorithms ⋮ Bounds on Fixed Input/Output Length Post-processing Functions for Biased Physical Random Number Generators ⋮ On hitting-set generators for polynomials that vanish rarely ⋮ Reed-Muller Codes
Cites Work
- Unnamed Item
- Unnamed Item
- Generating quasi-random sequences from semi-random sources
- On using deterministic functions to reduce randomness in probabilistic algorithms
- Expanders, randomness, or time versus space
- Expanders that beat the eigenvalue bound: Explicit construction and applications
- Hardness vs randomness
- Decoding of Reed Solomon codes beyond the error-correction bound
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Perfect information leader election in \(\log^*n+O(1)\) rounds
- On the complexity of approximating the VC dimension.
- Randomness is linear in space
- Simulating BPP using a general weak random source
- Pseudorandom generators without the XOR Lemma (extended abstract)
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Extractors and pseudo-random generators with optimal seed length
- Extractor Codes
- Better extractors for better codes?
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Simple Constructions of Almost k-wise Independent Random Variables
- Computing with Very Weak Random Sources
- Combinatorial bounds for list decoding
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Loss-less condensers, unbalanced expanders, and extractors
- Extractors and pseudorandom generators
- Extracting Randomness via Repeated Condensing
- Extracting all the randomness and reducing the error in Trevisan's extractors
- Pseudo-random generators for all hardnesses
