Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Applied Mathematics & Information Sciences

Generalized Upper Bound of Agreement Probability for Extracting Common Random Bits From Correlated Sources

Young-Sik Kim, Dae‐Woon Lim

Published Oct 9, 2013• 0 citations
Publisher

Abstract

Abstract: Suppose that both Alice and Bob receive independent random bits without any bias, which are influenced by an independent noise. From the received random bits, Alice and Bob are willing to extract common randomness, without any communication. The extracted common randomness can be used for authentication or secrets. Recently, Bogdanov and Mossel derived an upper bound of the agreement probability, based on the min-entropy of outputs. In this paper, we derive a generalized upper bound of the probability of extracting common random bits from correlated sources, using the Rènyi entropy of order 1/(1−ε), where ε is the error probability of the binary symmetric noise. It is shown that the generalized upper bound is always less than or equal to the previous bound.

DOI
10.12785/amis/080226

Related papers

On Extracting Common Random Bits From Correlated Sources on Large Alphabets

Siu On Chan, Elchanan Mossel, Joe Neeman

Suppose Alice and Bob receive strings X=(X1,...,Xn) and Y=(Y1,...,Yn) each uniformly random in [s]n, but so that X and Y are correlated. For each symbol i, we have that Yi=Xiwith probability 1-ε and otherwise Yiis chosen independently and uniformly from [s]. Alice and Bob wish to use their respective strings to extract a uniformly chosen common sequence from [s]k, but without communicating. How well can they do? The trivial strategy of outputting the first k symbols yields an agreement probability of (1-ε+ε/s)k. In a recent work by Bogdanov and Mossel, it was shown that in the binary case where s=2 and k=k(ε) is large enough then it is possible to extract k bits with a better agreement probability rate. In particular, it is possible to achieve agreement probability (kε)-1/2·2-kε/(2(1-ε/2))using a random construction based on Hamming balls, and this is optimal up to lower order terms. In this paper, we consider the same problem over larger alphabet sizes s and we show that the agreement probability rate changes dramatically as the alphabet grows. In particular, we show no strategy can achieve agreement probability better than (1-ε)k(1+δ(s))kwhere δ(s)→ 0 as s→∞. We also show that Hamming ball-based constructions have much lower agreement probability rate than the trivial algorithm as s→∞. Our proofs and results are intimately related to subtle properties of hypercontractive inequalities.

arXiv:1208.5946•IEEE Transactions on Information Theory•Jan 31, 2014•16 citations

On Extracting Common Random Bits From Correlated Sources

Andrej Bogdanov, Elchanan Mossel

Suppose Alice and Bob receive strings of unbiased independent but noisy bits from some random source. They wish to use their respective strings to extract a common sequence of random bits with high probability but without communicating. How many such bits can they extract? The trivial strategy of outputting the first$k$bits yields an agreement probability of$(1-\varepsilon)^{k}<2^{-1.44k\varepsilon}$, where$\varepsilon$is the amount of noise. We show that no strategy can achieve agreement probability better than$2^{-k\varepsilon/(1-\varepsilon)}$.

arXiv:1007.2315•IEEE Transactions on Information Theory•Oct 1, 2011•39 citations

Tight Bounds for Communication-Assisted Agreement Distillation

Venkatesan Guruswami, Jaikumar Radhakrishnan

Suppose Alice holds a uniformly random string X in {0,1}^N and Bob holds a noisy version Y of X where each bit of X is flipped independently with probability epsilon in [0,1/2]. Alice and Bob would like to extract a common random string of min-entropy at least k. In this work, we establish the communication versus success probability trade-off for this problem by giving a protocol and a matching lower bound (under the restriction that the string to be agreed upon is determined by Alice's input X). Specifically, we prove that in order for Alice and Bob to agree on a common string with probability 2^{-gamma k} (gamma k >= 1), the optimal communication (up to o(k) terms, and achievable for large N) is precisely (C *(1-gamma) - 2 * sqrt{ C * (1-C) gamma}) * k, where C := 4 * epsilon * (1-epsilon). In particular, the optimal communication to achieve Omega(1) agreement probability approaches 4 * epsilon * (1-epsilon) * k. We also consider the case when Y is the output of the binary erasure channel on X, where each bit of Y equals the corresponding bit of X with probability 1-epsilon and is otherwise erased (that is, replaced by a "?"). In this case, the communication required becomes (epsilon * (1-gamma) - 2 * sqrt{ epsilon * (1-epsilon) * gamma}) * k. In particular, the optimal communication to achieve Omega(1) agreement probability approaches epsilon * k, and with no communication the optimal agreement probability approaches 2^{- (1-sqrt{1-epsilon})/(1+sqrt{1-epsilon}) * k}. Our protocols are based on covering codes and extend the approach of (Bogdanov and Mossel, 2011) for the zero-communication case. Our lower bounds rely on hypercontractive inequalities. For the model of bit-flips, our argument extends the approach of (Bogdanov and Mossel, 2011) by allowing communication; for the erasure model, to the best of our knowledge the needed hypercontractivity statement was not studied before, and it was established (given our application) by (Nair and Wang 2015). We also obtain information complexity lower bounds for these tasks, and together with our protocol, they shed light on the recently popular "most informative Boolean function" conjecture of Courtade and Kumar.

Leibniz international proceedings in informatics•Jan 1, 2016•13 citations

Tight bounds for communication assisted agreement distillation.

Venkatesan Guruswami, Jaikumar Radhakrishnan

Suppose Alice holds a uniformly random string X ∈ {0, 1}N and Bob holds a noisy version Y of X where each bit of X is flipped independently with probability e ∈ [0, 1/2]. Alice and Bob would like to extract a common random string of min-entropy at least k. In this work, we establish the communication versus success probability trade-off for this problem by giving a protocol and a matching lower bound (under the restriction that the string to be agreed upon is determined by Alice's input X). Specifically, we prove that in order for Alice and Bob to agree on a common string with probability 2-γk (γk ≥ 1), the optimal communication (up to o(k) terms, and achievable for large N) is precisely [EQUATION], where C:= 4e(1 - e). In particular, the optimal communication to achieve Ω(1) agreement probability approaches 4e(1 - e)k. We also consider the case when Y is the output of the binary erasure channel on X, where each bit of Y equals the corresponding bit of X with probability 1 - e and is otherwise erased (that is, replaced by a '?'). In this case, the communication required becomes [EQUATION]. In particular, the optimal communication to achieve Ω(1) agreement probability approaches ek, and with no communication the optimal agreement probability approaches [EQUATION]. Our protocols are based on covering codes and extend the approach of (Bogdanov and Mossel, 2011) for the zero-communication case. Our lower bounds rely on hypercontractive inequalities. For the model of bit-flips, our argument extends the approach of (Bogdanov and Mossel, 2011) by allowing communication; for the erasure model, to the best of our knowledge the needed hypercontractivity statement was not studied before, and it was established (given our application) by (Nair and Wang 2015). We also obtain information complexity lower bounds for these tasks, and together with our protocol, they shed light on the recently popular most informative Boolean function conjecture of Courtade and Kumar.

Electronic colloquium on computational complexity•Jan 1, 2016•4 citations

Common Randomness Generation from Sources with Countable Alphabet

Wafa Labidi, Rami Ezzine, Christian Deppe +2 more

We study a two-source model for common randomness (CR) generation in which the sender Alice and the receiver Bob generate a common random variable with a high probability of agreement by observing independent and identically distributed (i.i.d.) samples of correlated sources on countably infinite alphabets. The two parties are additionally allowed to communicate over a noisy memoryless channel. In our work, we establish a single-letter lower and upper-bound on the CR capacity for the proposed model. This is a challenging scenario because some of the finite alphabet properties, namely of the entropy can not be extended to the countably infinite case. We use a generalized typicality criterion, called unified typicality, which can be applied to random variables on countably infinite alphabets.

arXiv:2210.04556•International Conference on Communications•May 28, 2023•2 citations

A Lower and Upper Bound on the Epsilon-Uniform Common Randomness Capacity

Rami Ezzine, Moritz Wiese, Christian Deppe +1 more

We consider a standard two-source model for uniform common randomness (UCR) generation, in which Alice and Bob observe independent and identically distributed (i. i. d.) samples of a correlated finite source and where Alice is allowed to send information to Bob over an arbitrary single-user channel. We study the ϵ-UCR capacity for the proposed model, defined as the maximum common randomness rate one can achieve such that the probability that Alice and Bob do not agree on a common uniform or nearly uniform random variable does not exceed ϵ. We establish a lower and an upper bound on the ϵ-UCR capacity using the bounds on the ϵ-transmission capacity proved by Verdú and Han for arbitrary point-to-point channels.A detailed version with all proofs, explanations and more discussions can be found in [1].

arXiv:2305.05524•IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2023•5 citations
Abstract: Suppose that both Alice and Bob receive independent random bits without any bias, which are influenced by an independent noise. From the received random bits, Alice and Bob are willing to extract common randomness, without any communication. The extracted common randomness can be used for authentication or secrets. Recently, Bogdanov and Mossel derived an upper bound of the agreement probability, based on the min-entropy of outputs. In this paper, we derive a generalized upper bound of the probability of extracting common random bits from correlated sources, using the Rènyi entropy of order 1/(1−ε), where ε is the error probability of the binary symmetric noise. It is shown that the generalized upper bound is always less than or equal to the previous bound.
Suppose Alice and Bob receive strings X=(X1,...,Xn) and Y=(Y1,...,Yn) each uniformly random in [s]n, but so that X and Y are correlated. For each symbol i, we have that Yi=Xiwith probability 1-ε and otherwise Yiis chosen independently and uniformly from [s]. Alice and Bob wish to use their respective strings to extract a uniformly chosen common sequence from [s]k, but without communicating. How well can they do? The trivial strategy of outputting the first k symbols yields an agreement probability of (1-ε+ε/s)k. In a recent work by Bogdanov and Mossel, it was shown that in the binary case where s=2 and k=k(ε) is large enough then it is possible to extract k bits with a better agreement probability rate. In particular, it is possible to achieve agreement probability (kε)-1/2·2-kε/(2(1-ε/2))using a random construction based on Hamming balls, and this is optimal up to lower order terms. In this paper, we consider the same problem over larger alphabet sizes s and we show that the agreement probability rate changes dramatically as the alphabet grows. In particular, we show no strategy can achieve agreement probability better than (1-ε)k(1+δ(s))kwhere δ(s)→ 0 as s→∞. We also show that Hamming ball-based constructions have much lower agreement probability rate than the trivial algorithm as s→∞. Our proofs and results are intimately related to subtle properties of hypercontractive inequalities.
Suppose Alice and Bob receive strings of unbiased independent but noisy bits from some random source. They wish to use their respective strings to extract a common sequence of random bits with high probability but without communicating. How many such bits can they extract? The trivial strategy of outputting the firstkkkbits yields an agreement probability of(1−ε)k<2−1.44kε(1-\varepsilon)^{k}<2^{-1.44k\varepsilon}(1−ε)k<2−1.44kε, whereε\varepsilonεis the amount of noise. We show that no strategy can achieve agreement probability better than2−kε/(1−ε)2^{-k\varepsilon/(1-\varepsilon)}2−kε/(1−ε).
Suppose Alice holds a uniformly random string X in {0,1}^N and Bob holds a noisy version Y of X where each bit of X is flipped independently with probability epsilon in [0,1/2]. Alice and Bob would like to extract a common random string of min-entropy at least k. In this work, we establish the communication versus success probability trade-off for this problem by giving a protocol and a matching lower bound (under the restriction that the string to be agreed upon is determined by Alice's input X). Specifically, we prove that in order for Alice and Bob to agree on a common string with probability 2^{-gamma k} (gamma k >= 1), the optimal communication (up to o(k) terms, and achievable for large N) is precisely (C *(1-gamma) - 2 * sqrt{ C * (1-C) gamma}) * k, where C := 4 * epsilon * (1-epsilon). In particular, the optimal communication to achieve Omega(1) agreement probability approaches 4 * epsilon * (1-epsilon) * k. We also consider the case when Y is the output of the binary erasure channel on X, where each bit of Y equals the corresponding bit of X with probability 1-epsilon and is otherwise erased (that is, replaced by a "?"). In this case, the communication required becomes (epsilon * (1-gamma) - 2 * sqrt{ epsilon * (1-epsilon) * gamma}) * k. In particular, the optimal communication to achieve Omega(1) agreement probability approaches epsilon * k, and with no communication the optimal agreement probability approaches 2^{- (1-sqrt{1-epsilon})/(1+sqrt{1-epsilon}) * k}. Our protocols are based on covering codes and extend the approach of (Bogdanov and Mossel, 2011) for the zero-communication case. Our lower bounds rely on hypercontractive inequalities. For the model of bit-flips, our argument extends the approach of (Bogdanov and Mossel, 2011) by allowing communication; for the erasure model, to the best of our knowledge the needed hypercontractivity statement was not studied before, and it was established (given our application) by (Nair and Wang 2015). We also obtain information complexity lower bounds for these tasks, and together with our protocol, they shed light on the recently popular "most informative Boolean function" conjecture of Courtade and Kumar.
Suppose Alice holds a uniformly random string X ∈ {0, 1}N and Bob holds a noisy version Y of X where each bit of X is flipped independently with probability e ∈ [0, 1/2]. Alice and Bob would like to extract a common random string of min-entropy at least k. In this work, we establish the communication versus success probability trade-off for this problem by giving a protocol and a matching lower bound (under the restriction that the string to be agreed upon is determined by Alice's input X). Specifically, we prove that in order for Alice and Bob to agree on a common string with probability 2-γk (γk ≥ 1), the optimal communication (up to o(k) terms, and achievable for large N) is precisely [EQUATION], where C:= 4e(1 - e). In particular, the optimal communication to achieve Ω(1) agreement probability approaches 4e(1 - e)k. We also consider the case when Y is the output of the binary erasure channel on X, where each bit of Y equals the corresponding bit of X with probability 1 - e and is otherwise erased (that is, replaced by a '?'). In this case, the communication required becomes [EQUATION]. In particular, the optimal communication to achieve Ω(1) agreement probability approaches ek, and with no communication the optimal agreement probability approaches [EQUATION]. Our protocols are based on covering codes and extend the approach of (Bogdanov and Mossel, 2011) for the zero-communication case. Our lower bounds rely on hypercontractive inequalities. For the model of bit-flips, our argument extends the approach of (Bogdanov and Mossel, 2011) by allowing communication; for the erasure model, to the best of our knowledge the needed hypercontractivity statement was not studied before, and it was established (given our application) by (Nair and Wang 2015). We also obtain information complexity lower bounds for these tasks, and together with our protocol, they shed light on the recently popular most informative Boolean function conjecture of Courtade and Kumar.
We study a two-source model for common randomness (CR) generation in which the sender Alice and the receiver Bob generate a common random variable with a high probability of agreement by observing independent and identically distributed (i.i.d.) samples of correlated sources on countably infinite alphabets. The two parties are additionally allowed to communicate over a noisy memoryless channel. In our work, we establish a single-letter lower and upper-bound on the CR capacity for the proposed model. This is a challenging scenario because some of the finite alphabet properties, namely of the entropy can not be extended to the countably infinite case. We use a generalized typicality criterion, called unified typicality, which can be applied to random variables on countably infinite alphabets.
We consider a standard two-source model for uniform common randomness (UCR) generation, in which Alice and Bob observe independent and identically distributed (i. i. d.) samples of a correlated finite source and where Alice is allowed to send information to Bob over an arbitrary single-user channel. We study the ϵ-UCR capacity for the proposed model, defined as the maximum common randomness rate one can achieve such that the probability that Alice and Bob do not agree on a common uniform or nearly uniform random variable does not exceed ϵ. We establish a lower and an upper bound on the ϵ-UCR capacity using the bounds on the ϵ-transmission capacity proved by Verdú and Han for arbitrary point-to-point channels.A detailed version with all proofs, explanations and more discussions can be found in [1].