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

Electronic colloquium on computational complexity

Tight bounds for communication assisted agreement distillation.

Venkatesan Guruswami, Jaikumar Radhakrishnan

Published Jan 1, 2016• 3 citations
OpenAlex

Abstract

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.

Related papers

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•11 citations

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.

IEEE Transactions on Information Theory•Jan 31, 2014•14 citations

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=(X_1,...,X_n)$ and $Y=(Y_1,...,Y_n)$ each uniformly random in $[s]^n$ but so that $X$ and $Y$ are correlated . For each symbol $i$, we have that $Y_i = X_i$ with probability $1-\eps$ and otherwise $Y_i$ is 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 - \eps + \eps/s)^k$. In a recent work by Bogdanov and Mossel it was shown that in the binary case where $s=2$ and $k = k(\eps)$ 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\eps)^{-1/2} \cdot 2^{-k\eps/(2(1 - \eps/2))}$ using a random construction based on Hamming balls, and this is optimal up to lower order terms. In the current 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-\eps)^k (1+δ(s))^k$ where $δ(s) \to 0$ as $s \to \infty$. We also show that Hamming ball based constructions have {\em much lower} agreement probability rate than the trivial algorithm as $s \to \infty$. Our proofs and results are intimately related to subtle properties of hypercontractive inequalities.

arXiv:1208.5946•Aug 29, 2012•0 citations

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

Young-Sik Kim, Dae‐Woon Lim

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.

Applied Mathematics & Information Sciences•Oct 9, 2013•0 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)}$.

IEEE Transactions on Information Theory•Oct 1, 2011•37 citations

Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem

Mark Bun, Joao F. Doriguello, John Kallaugher +1 more

We study the one-way communication complexity of the $f$-Boolean Hidden Partition problem. Here, Alice is given an $n$-bit string and Bob is given $Ω(n)$ disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of $f$ on these blocks either agree with all of the labels or disagree with all of them, Bob must determine which is the case using a single message from Alice. This problem generalizes the Boolean Hidden Matching and Hidden Hypermatching problems, which capture the special case where $f$ is the parity function. We establish classical and quantum communication bounds for $f$-Boolean Hidden Partition in terms of the sign degree $d$ of $f$, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when $d \le 1$ and quantum protocols when $d \le 2$, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every $f$ of sign degree $d \ge 2$, the randomized classical communication complexity of this problem is $Θ(n^{1-1/d})$ while its quantum communication complexity lies between $Ω(n^{1-2/d})$ and $\bO{n^{1-1/\lceil d/2 \rceil} \log n}$. This completely characterizes the functions $f$ admitting polynomial quantum advantage as those for which $d \ge 2$, with a new infinite family of exponential separations given by the case $d = 2$.

quant-pharXiv:2610.06789•Oct 6, 2026•0 citations
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.
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 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 X=(X1,...,Xn)X=(X_1,...,X_n)X=(X1​,...,Xn​) and Y=(Y1,...,Yn)Y=(Y_1,...,Y_n)Y=(Y1​,...,Yn​) each uniformly random in [s]n[s]^n[s]n but so that XXX and YYY are correlated . For each symbol iii, we have that Yi=XiY_i = X_iYi​=Xi​ with probability $1-\eps$ and otherwise YiY_iYi​ is chosen independently and uniformly from [s][s][s]. Alice and Bob wish to use their respective strings to extract a uniformly chosen common sequence from [s]k[s]^k[s]k but without communicating. How well can they do? The trivial strategy of outputting the first kkk symbols yields an agreement probability of $(1 - \eps + \eps/s)^k$. In a recent work by Bogdanov and Mossel it was shown that in the binary case where s=2s=2s=2 and $k = k(\eps)$ is large enough then it is possible to extract kkk bits with a better agreement probability rate. In particular, it is possible to achieve agreement probability $(k\eps)^{-1/2} \cdot 2^{-k\eps/(2(1 - \eps/2))}$ using a random construction based on Hamming balls, and this is optimal up to lower order terms. In the current paper we consider the same problem over larger alphabet sizes sss 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-\eps)^k (1+δ(s))^k$ where δ(s)→0δ(s) \to 0δ(s)→0 as s→∞s \to \inftys→∞. We also show that Hamming ball based constructions have {\em much lower} agreement probability rate than the trivial algorithm as s→∞s \to \inftys→∞. Our proofs and results are intimately related to subtle properties of hypercontractive inequalities.
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 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−ε).
We study the one-way communication complexity of the fff-Boolean Hidden Partition problem. Here, Alice is given an nnn-bit string and Bob is given Ω(n)Ω(n)Ω(n) disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of fff on these blocks either agree with all of the labels or disagree with all of them, Bob must determine which is the case using a single message from Alice. This problem generalizes the Boolean Hidden Matching and Hidden Hypermatching problems, which capture the special case where fff is the parity function. We establish classical and quantum communication bounds for fff-Boolean Hidden Partition in terms of the sign degree ddd of fff, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when d≤1d \le 1d≤1 and quantum protocols when d≤2d \le 2d≤2, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every fff of sign degree d≥2d \ge 2d≥2, the randomized classical communication complexity of this problem is Θ(n1−1/d)Θ(n^{1-1/d})Θ(n1−1/d) while its quantum communication complexity lies between Ω(n1−2/d)Ω(n^{1-2/d})Ω(n1−2/d) and $\bO{n^{1-1/\lceil d/2 \rceil} \log n}$. This completely characterizes the functions fff admitting polynomial quantum advantage as those for which d≥2d \ge 2d≥2, with a new infinite family of exponential separations given by the case d=2d = 2d=2.