Deterministic Randomness Extraction from Generalized and Distributed Santha--Vazirani Sources

DOI10.1137/15M1027206zbMath1394.68147OpenAlexW2575748501MaRDI QIDQ2956041

Omid Etesami, Amin Gohari, Salman Beigi

Publication date: 16 January 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1027206

zbMATH Keywords

randomness extractionSantha-Vazirani sourcescommon randomness extraction

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Combinatorial probability (60C05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Learning under \(p\)-tampering poisoning attacks, Unnamed Item, How to extract useful randomness from unreliable sources

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extractors and rank extractors for polynomial sources
• On the construction of affine extractors
• Generating quasi-random sequences from semi-random sources
• A lower bound for the time to assure interactive consistency
• Independent unbiased coin flips from a correlated biased source - a finite state Markov chain
• Randomness is linear in space
• Extractors for varieties
• Deterministic extraction from weak random sources.
• On the Impossibility of Cryptography with Tamperable Randomness
• On Sequences of Pairs of Dependent Random Variables
• New Monotones and Lower Bounds in Unconditional Two-Party Computation
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources
• MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
• The source coding game
• Deterministic extractors for small-space sources