Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

1988/04/01 by Benny Chor, Oded Goldreich · 559 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #Communication complexity #Computability, Logic, AI Algorithms #Computer science #DNA and Biological Computing #Discrete mathematics #Mathematics #Probabilistic analysis of algorithms #Probabilistic logic #Randomness #Robustness (evolution) #Statistics #Theoretical computer science #Wireless Communication Security Techniques

paper · doi:10.1137/0217015

published in SIAM Journal on Computing 17(2), 230-261 (Society for Industrial and Applied Mathematics)

openalex publication_date 1988/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Abstract

A new model for weak random physical sources is presented. The new model strictly generalizes previous models (e.g., the Santha and Vazirani model [27]). The sources considered output strings according to probability distributions in which no single string is too probable. The new model provides a fruitful viewpoint on problems studied previously such as: • Extracting almost-perfect bits from sources of weak randomness. The question of possibility as well as the question of efficiency of such extraction schemes are addressed. • Probabilistic communication complexity. It is shown that most functions have linear communication complexity in a very strong probabilistic sense. • Robustness of BPP with respect to sources of weak randomness (generalizing a result of Vazirani and Vazirani [32], [33]).

Cited by

• Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
• On the Power of Quantum Computation
• What graph neural networks cannot learn: depth vs width
• Provable limitations of deep learning
• Extractors in Paley graphs: a random model
• Tight Bounds for Hashing Block Sources
• Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs
• The decoupling approach to quantum information theory
• Exponential separations for one-way quantum communication complexity, with applications to cryptography
• Additive combinatorics with a view towards computer science and cryptography: An exposition
• A lower bound for bounded round quantum communication complexity of set disjointness
• Quantum vs. Classical Communication and Computation
• Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols
• Space Lower Bounds for Online Pattern Matching
• Improved Extractors for Affine Lines
• Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification
• Poly-time universality and limitations of deep learning
• Anti-concentration in most directions
• Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications
• Two-Source Extractors Secure Against Quantum Adversaries
• Paley-like graphs for the Ramsey number r(C₄,K_t)
• Improved Constructions of Two-Source Extractors
• An Introduction to Quantum Complexity Theory
• Guest column
• Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors
• Quantum vs. classical communication and computation
• Robust amplification of Santha-Vazirani sources with three devices
• Linear degree extractors and the inapproximability of max clique and chromatic number
• A Pseudorandom Generator from any One-way Function
• Performance Optimization on Practical Quantum Random Number Generators: Modification on Min-entropy Evaluation and Acceleration on Post Processing

Related

• On extracting common random bits from correlated sources
• No-signaling-proof randomness extraction from public weak sources
• Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources
• Efficient Generation of Random Bits from Finite State Markov Chains
• Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions