Extractors from Reed-Muller codes
DOI10.1016/J.JCSS.2005.05.010zbMATH Open1094.68036DBLPjournals/jcss/Ta-ShmaZS06OpenAlexW1556285486WikidataQ62398473 ScholiaQ62398473MaRDI QIDQ2496317FDOQ2496317
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Hardness vs randomness
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- On the complexity of approximating the VC dimension.
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Simple Constructions of Almost k-wise Independent Random Variables
- Generating quasi-random sequences from semi-random sources
- Simulating BPP using a general weak random source
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Decoding of Reed Solomon codes beyond the error-correction bound
- Extractor Codes
- Perfect information leader election in \(\log^*n+O(1)\) rounds
- Randomness is linear in space
- Loss-less condensers, unbalanced expanders, and extractors
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Pseudo-random generators for all hardnesses
- Extractors and pseudorandom generators
- Pseudorandom generators without the XOR lemma (extended abstract)
- Extracting Randomness via Repeated Condensing
- Computing with Very Weak Random Sources
- Combinatorial bounds for list decoding
- Expanders that beat the eigenvalue bound: Explicit construction and applications
- Extracting all the randomness and reducing the error in Trevisan's extractors
- On using deterministic functions to reduce randomness in probabilistic algorithms
- Expanders, randomness, or time versus space
- Extractors and pseudo-random generators with optimal seed length
- Better extractors for better codes?
Cited In (17)
- On hitting-set generators for polynomials that vanish rarely
- Robustly reusable fuzzy extractor with imperfect randomness
- Pseudo-random generators for all hardnesses
- Deterministic extractors for affine sources over large fields
- Title not available (Why is that?)
- Another Motivation for Reducing the Randomness Complexity of Algorithms
- Extracting Kolmogorov complexity with applications to dimension zero-one laws
- On the complexity of approximating the VC dimension.
- Local List Recovery of High-Rate Tensor Codes and Applications
- Bounds on Fixed Input/Output Length Post-processing Functions for Biased Physical Random Number Generators
- Simple extractors via constructions of cryptographic pseudo-random generators
- Reed-Muller Codes
- Reconstructive dispersers and hitting set generators
- A modular framework for quantum-proof randomness extractors
- Title not available (Why is that?)
- Nearly optimal pseudorandomness from hardness
- An Introduction to Randomness Extractors
Recommendations
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Reed‐muller codes: an ideal theory approach 👍 👎
- Reed-Muller codes and permutation decoding 👍 👎
- On the Reed-Muller codes 👍 👎
- Efficiently Decoding Reed–Muller Codes From Random Errors 👍 👎
- Efficiently decoding Reed-Muller codes from random errors 👍 👎
- Reed–Muller Codes: Theory and Algorithms 👍 👎
- Reed-Muller Codes 👍 👎
This page was built for publication: Extractors from Reed-Muller codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2496317)
