Extracting randomness: A survey and new constructions

DOI10.1006/jcss.1997.1546zbMath0943.68190OpenAlexW1986686371WikidataQ62398501 ScholiaQ62398501MaRDI QIDQ1305929

Noam Nisan, Amnon Ta-Shma

Publication date: 17 February 2000

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1997.1546

zbMATH Keywords

Boolean functionsextractors

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Related Items (24)

On the complexity of approximating the VC dimension. ⋮ Deterministic extractors for affine sources over large fields ⋮ Estimating gaps in martingales and applications to coin-tossing: constructions and hardness ⋮ Lower and upper bounds on the randomness complexity of private computations of AND ⋮ Source-device-independent randomness expansion using quantum random access codes ⋮ Random sources in private computation ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ How to get more mileage from randomness extractors ⋮ Weak derandomization of weak algorithms: explicit versions of Yao's lemma ⋮ Quantum Cryptography: Key Distribution and Beyond ⋮ Deterministic extractors for small-space sources ⋮ An Introduction to Randomness Extractors ⋮ Proved Random Numbers Obtained from Hardware Devices ⋮ Improving the Hadamard extractor ⋮ Optimal Coin Flipping ⋮ Pseudorandom generators without the XOR lemma ⋮ Extracting Kolmogorov complexity with applications to dimension zero-one laws ⋮ A joint Shannon cipher and privacy amplification approach to attaining exponentially decaying information leakage ⋮ Coalgebraic tools for randomness-conserving protocols ⋮ On the tight security of TLS 1.3: theoretically sound cryptographic parameters for real-world deployments ⋮ Non-interactive timestamping in the bounded-storage model ⋮ Bounds on Fixed Input/Output Length Post-processing Functions for Biased Physical Random Number Generators ⋮ Lower and Upper Bounds on the Randomness Complexity of Private Computations of AND ⋮ Semi-device-independent randomness certification with partially free random sources using \(4\rightarrow 1\) quantum random access code

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A geometric construction of a superconcentrator of depth 2
• Some extremal problems arising from discrete control processes
• Generating quasi-random sequences from semi-random sources
• Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
• Expanders, randomness, or time versus space
• On the power of two-point based sampling
• Superconcentrators of depth 2
• Explicit constructions of linear-sized superconcentrators
• Independent unbiased coin flips from a correlated biased source - a finite state Markov chain
• Tiny families of functions with random properties (preliminary version)
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Sorting and Selecting in Rounds
• Simple Constructions of Almost k-wise Independent Random Variables
• Superconcentrators
• Computing with Very Weak Random Sources
• Interactive proofs and the hardness of approximating cliques
• More deterministic simulation in logspace
• Expanders that beat the eigenvalue bound

This page was built for publication: Extracting randomness: A survey and new constructions