Extracting Randomness Using Few Independent Sources
DOI10.1137/S0097539705447141zbMATH Open1127.68030OpenAlexW1980688410MaRDI QIDQ5757459FDOQ5757459
Authors: Boaz Barak, Russell Impagliazzo, A. Wigderson 
Publication date: 7 September 2007
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539705447141
Recommendations
- Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors
- Simulating independence
- 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
- Extractors with weak random seeds
- 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Generalized Ramsey theory (05C55) Exponential sums (11T23)
Cited In (39)
- Extractors in Paley graphs: a random model
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one
- Deterministic extractors for affine sources over large fields
- The sum-product theorem in \(\mathbb Z_q\) with \(q\) arbitrary
- Deterministic extractors for small-space sources
- An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy
- 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
- A product theorem in free groups.
- Improving the Hadamard extractor
- No time to hash: on super-efficient entropy accumulation
- Increasing the output length of zero-error dispersers
- Deterministic extractors for additive sources (extended abstract)
- New results on sum-product type growth over fields
- From affine to two-source extractors via approximate duality
- Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors
- Bounds on Fixed Input/Output Length Post-processing Functions for Biased Physical Random Number Generators
- Growth in groups: ideas and perspectives
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- Proved random numbers obtained from hardware devices
- Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs
- Extractors and lower bounds for locally samplable sources
- Extractors for sumset sources
- Interactions of computational complexity theory and mathematics
- Zero-fixing extractors for sub-logarithmic entropy
- An explicit two-source extractor with min-entropy rate near $4/9$
- Explicit two-source extractors and resilient functions
- Extracting Computational Entropy and Learning Noisy Linear Functions
- Extracting randomness from extractor-dependent sources
- Extractors for small zero-fixing sources
- Extracting Randomness via Repeated Condensing
- Title not available (Why is that?)
- An introduction to randomness extractors
- Non-malleability against polynomial tampering
- Increasing the Output Length of Zero-Error Dispersers
- Sparse affine-invariant linear codes are locally testable
- Extractors for a constant number of polynomially small MIN-entropy independent sources
- From affine to two-source extractors via approximate duality
- Optimal bounds for single-source Kolmogorov extractors
This page was built for publication: Extracting Randomness Using Few Independent Sources
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5757459)
