Deterministic randomness extraction from generalized and distributed Santha-Vazirani sources

DOI10.1007/978-3-662-47672-7_12MaRDI QIDQ3448780zbMATH OpenOpenAlexFDO

Authors Salman Beigi, Omid Etesami, Amin Gohari

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.6641

Mathematics Subject Classification ID

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

Abstract: A Santha-Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani show that deterministic randomness extraction from these sources is impossible. In this paper, we study the generalization of SV sources for non-binary sequences. We show that unlike the binary case, deterministic randomness extraction in the generalized case is sometimes possible. We present a necessary condition and a sufficient condition for the possibility of deterministic randomness extraction. These two conditions coincide in "non-degenerate" cases. Next, we turn to a distributed setting. In this setting the SV source consists of a random sequence of pairs $(a_1,b_1),(a_2,b_2),ldots$ distributed between two parties, where the first party receives $a_i$'s and the second one receives $b_i$'s. The goal of the two parties is to extract common randomness without communication. Using the notion of maximal correlation, we prove a necessary condition and a sufficient condition for the possibility of common randomness extraction from these sources. Based on these two conditions, the problem of common randomness extraction essentially reduces to the problem of randomness extraction from (non-distributed) SV sources. This result generalizes results of G'acs and K"orner, and Witsenhausen about common randomness extraction from i.i.d. sources to adversarial sources.

Recommendations

• Deterministic randomness extraction from generalized and distributed Santha-Vazirani sources
• Optimal deterministic extractors for generalized Santha-Vazirani sources
• Santha-Vazirani sources, deterministic condensers and very strong extractors
• Deterministic Extractors for Independent-Symbol Sources
• How to get more mileage from randomness extractors

Cites work

• A lower bound for the time to assure interactive consistency
• Deterministic extractors for affine sources over large fields
• Deterministic extractors for small-space sources
• Deterministic randomness extraction from generalized and distributed Santha-Vazirani sources
• Extractors and rank extractors for polynomial sources
• Extractors for a constant number of polynomially small MIN-entropy independent sources
• Extractors for varieties
• Generating quasi-random sequences from semi-random sources
• scientific article; zbMATH DE number 3497786 (Why is no real title available?)
• scientific article; zbMATH DE number 1097580 (Why is no real title available?)
• scientific article; zbMATH DE number 3201090 (Why is no real title available?)
• Independent unbiased coin flips from a correlated biased source - a finite state Markov chain
• MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
• On Sequences of Pairs of Dependent Random Variables
• On the construction of affine extractors
• On the impossibility of cryptography with tamperable randomness
• Randomness is linear in space
• The source coding game
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(5)

• Santha-Vazirani sources, deterministic condensers and very strong extractors
• Deterministic randomness extraction from generalized and distributed Santha-Vazirani sources
• Deterministic randomness extraction from generalized and distributed Santha-Vazirani sources
• Optimal deterministic extractors for generalized Santha-Vazirani sources
• Multi-source randomness extraction and generation in the random-oracle model

This page was built for publication: Deterministic randomness extraction from generalized and distributed Santha-Vazirani sources

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448780)