An Introduction to Randomness Extractors
From MaRDI portal
Publication:3012907
DOI10.1007/978-3-642-22012-8_2zbMath1333.68289OpenAlexW18818645MaRDI QIDQ3012907
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
Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Randomness extraction in computability theory ⋮ From graphs to keyed quantum hash functions ⋮ Zero-Fixing Extractors for Sub-Logarithmic Entropy ⋮ Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Shannon Entropy Versus Renyi Entropy from a Cryptographic Viewpoint ⋮ Code generator matrices as RNG conditioners ⋮ Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture ⋮ A Better Chain Rule for HILL Pseudoentropy - Beyond Bounded Leakage ⋮ Efficient and Provable White-Box Primitives ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Clone-induced approximation algebras of Bernoulli distributions ⋮ Evaluating Entropy for True Random Number Generators: Efficient, Robust and Provably Secure ⋮ Property testing lower bounds via a generalization of randomized parity decision trees ⋮ Two-Source Randomness Extractors for Elliptic Curves for Authenticated Key Exchange ⋮ Unnamed Item ⋮ Algebras of probability distributions on finite sets ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ The Complexity of Differential Privacy ⋮ On extracting space-bounded Kolmogorov complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- Extractors and rank extractors for polynomial sources
- Affine extractors over prime fields
- On the construction of affine extractors
- Generating quasi-random sequences from semi-random sources
- Expanders that beat the eigenvalue bound: Explicit construction and applications
- Intersection theorems with geometric consequences
- Iterating von Neumann's procedure for extracting random bits
- The Shannon capacity of a union
- Extracting randomness: A survey and new constructions
- Hardness vs randomness
- Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs
- Almost optimal dispersers
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Independent unbiased coin flips from a correlated biased source - a finite state Markov chain
- A sum-product estimate in finite fields, and applications
- Randomness is linear in space
- Deterministic extractors for affine sources over large fields
- Lossless condensers, unbalanced expanders, and extractors
- Extractors from Reed-Muller codes
- 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
- Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
- Expander graphs and their applications
- How to get more mileage from randomness extractors
- Increasing the Output Length of Zero-Error Dispersers
- Extractors for Three Uneven-Length Sources
- Simple extractors for all min-entropies and a new pseudorandom generator
- Extractor Codes
- Randomness conductors and constant-degree lossless expanders
- Extractors
- Extractors with weak random seeds
- Pseudorandom Generators and Typically-Correct Derandomization
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Explicit OR-dispersers with polylogarithmic degree
- A Chernoff Bound for Random Walks on Expander Graphs
- Eigenvalues and expansion of regular graphs
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
- 2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness
- Affine dispersers from subspace polynomials
- Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources
- MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
- Computational Complexity
- From affine to two-source extractors via approximate duality
- Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient Cryptography
- Extractors and pseudorandom generators
- Dispersers for Affine Sources with Sub-polynomial Entropy
- The Efficient Construction of an Unbiased Random Sequence
- Deterministic Extractors for Bit‐Fixing Sources by Obtaining an Independent Seed
- Extracting Randomness Using Few Independent Sources
- Deterministic extractors for small-space sources
- Cryptography and Coding
- Algorithmic Results in List Decoding
- Simulating independence
- Extracting all the randomness and reducing the error in Trevisan's extractors
