An introduction to randomness extractors
From MaRDI portal
Publication:3012907
DOI10.1007/978-3-642-22012-8_2zbMATH Open1333.68289OpenAlexW18818645MaRDI QIDQ3012907FDOQ3012907
Authors: Ronen Shaltiel 
Publication date: 7 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22012-8_2
Recommendations
Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20)
Cites Work
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Computational Complexity
- Intersection theorems with geometric consequences
- Hardness vs randomness
- A sum-product estimate in finite fields, and applications
- Expander graphs and their applications
- Deterministic extractors for small-space sources
- Dispersers for Affine Sources with Sub-polynomial Entropy
- Generating quasi-random sequences from semi-random sources
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Title not available (Why is that?)
- Simple extractors for all min-entropies and a new pseudorandom generator
- Extractor Codes
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- Randomness is linear in space
- Eigenvalues and expansion of regular graphs
- MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
- Affine extractors over prime fields
- On the construction of affine extractors
- Deterministic extractors for affine sources over large fields
- 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
- Extractors and rank extractors for polynomial sources
- Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
- A Chernoff Bound for Random Walks on Expander Graphs
- Title not available (Why is that?)
- Randomness conductors and constant-degree lossless expanders
- Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
- The Shannon capacity of a union
- Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs
- Pseudorandom Generators and Typically-Correct Derandomization
- Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors
- Affine dispersers from subspace polynomials
- Extracting randomness: A survey and new constructions
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient Cryptography
- Deterministic Extractors for Bit‐Fixing Sources by Obtaining an Independent Seed
- Cryptography and Coding
- Iterating von Neumann's procedure for extracting random bits
- Lossless condensers, unbalanced expanders, and extractors
- The Efficient Construction of an Unbiased Random Sequence
- Extractors and pseudorandom generators
- From affine to two-source extractors via approximate duality
- Extractors with weak random seeds
- Extractors
- Extracting Randomness Using Few Independent Sources
- Extractors from Reed-Muller codes
- Expanders that beat the eigenvalue bound: Explicit construction and applications
- Extracting all the randomness and reducing the error in Trevisan's extractors
- Independent unbiased coin flips from a correlated biased source - a finite state Markov chain
- Almost optimal dispersers
- 2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness
- How to get more mileage from randomness extractors
- Increasing the Output Length of Zero-Error Dispersers
- Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources
- Algorithmic Results in List Decoding
- Extractors for Three Uneven-Length Sources
- Explicit OR-dispersers with polylogarithmic degree
Cited In (27)
- Title not available (Why is that?)
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- Shannon entropy versus Renyi entropy from a cryptographic viewpoint
- Property testing lower bounds via a generalization of randomized parity decision trees
- Paradigms for Unconditional Pseudorandom Generators
- From graphs to keyed quantum hash functions
- A better chain rule for HILL pseudoentropy -- beyond bounded leakage
- Randomness extractors -- applications and constructions
- Two-source randomness extractors for elliptic curves for authenticated key exchange
- On extracting space-bounded Kolmogorov complexity
- Title not available (Why is that?)
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- Title not available (Why is that?)
- Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
- Improving \(3N\) circuit complexity lower bounds
- Zero-fixing extractors for sub-logarithmic entropy
- Extractors with weak random seeds
- The complexity of differential privacy
- Evaluating Entropy for True Random Number Generators: Efficient, Robust and Provably Secure
- Efficient and Provable White-Box Primitives
- Randomness extraction in computability theory
- How to get more mileage from randomness extractors
- Title not available (Why is that?)
- Code generator matrices as RNG conditioners
- Deterministic extraction from weak random sources.
- Algebras of probability distributions on finite sets
- Clone-induced approximation algebras of Bernoulli distributions
This page was built for publication: An introduction to randomness extractors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012907)
