Extracting Randomness Using Few Independent Sources
From MaRDI portal
Publication:5757459
DOI10.1137/S0097539705447141zbMath1127.68030OpenAlexW1980688410MaRDI QIDQ5757459
Russell Impagliazzo, Boaz Barak, Avi 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
Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Exponential sums (11T23) Generalized Ramsey theory (05C55)
Related Items
A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one ⋮ Zero-Fixing Extractors for Sub-Logarithmic Entropy ⋮ No time to hash: on super-efficient entropy accumulation ⋮ From Affine to Two-Source Extractors via Approximate Duality ⋮ Deterministic extractors for affine sources over large fields ⋮ An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy ⋮ Extracting Computational Entropy and Learning Noisy Linear Functions ⋮ 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction ⋮ Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors ⋮ Interactions of computational complexity theory and mathematics ⋮ NEW RESULTS ON SUM‐PRODUCT TYPE GROWTH OVER FIELDS ⋮ A product theorem in free groups. ⋮ Increasing the Output Length of Zero-Error Dispersers ⋮ Deterministic extractors for small-space sources ⋮ An Introduction to Randomness Extractors ⋮ Proved Random Numbers Obtained from Hardware Devices ⋮ Improving the Hadamard extractor ⋮ Sparse affine-invariant linear codes are locally testable ⋮ Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences ⋮ Unnamed Item ⋮ Extractors in Paley graphs: a random model ⋮ The sum-product theorem in \(\mathbb Z_q\) with \(q\) arbitrary ⋮ Extractors and Lower Bounds for Locally Samplable Sources ⋮ Optimal bounds for single-source Kolmogorov extractors ⋮ Extracting randomness from extractor-dependent sources ⋮ Bounds on Fixed Input/Output Length Post-processing Functions for Biased Physical Random Number Generators ⋮ Explicit two-source extractors and resilient functions ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs ⋮ Increasing the output length of zero-error dispersers ⋮ Growth in groups: ideas and perspectives ⋮ Non-malleability against polynomial tampering
