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

arXiv:2511.21015

The communication complexity of distributed estimation

Parikshit Gopalan, Raghu Meka, Prasad Raghavendra, Mihir Singhal, Avi Wigderson

Published Nov 26, 2025• 0 citations
arXivHTMLPDF

Abstract

We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions $p$ and $q$ over domains $X$ and $Y$, respectively. Their goal is to estimate \[ \mathbb{E}_{x \sim p,\, y \sim q}[f(x, y)] \] to within additive error $\varepsilon$ for a bounded function $f$, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of $f$ and the error parameter $\varepsilon$. The random sampling approach -- estimating the mean by averaging $f$ over $O(1/\varepsilon^2)$ random samples -- requires $O(R(f)/\varepsilon^2)$ total communication, where $R(f)$ is the randomized communication complexity of $f$. We design a new debiasing protocol which improves the dependence on $1/\varepsilon$ to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.

DOI
10.48550/arxiv.2511.21015

Related papers

The communication complexity of non-signaling distributions

Julien Degorre, Marc Kaplan, Sophie Laplante +1 more

We study a model of communication complexity that encompasses many well-studied problems, including classical and quantum communication complexity, the complexity of simulating distributions arising from bipartite measurements of shared quantum states, and XOR games. In this model, Alice gets an input $x$, Bob gets an input $y$, and their goal is to each produce an output $a,b$ distributed according to some pre-specified joint distribution $p(a,b|x,y)$. Our results apply to any non-signaling distribution, that is, those where Alice's marginal distribution does not depend on Bob's input, and vice versa.~~~By taking a geometric view of the non-signaling distributions, we introduce a simple new technique based on affine combinations of lower-complexity distributions, and we give the first general technique to apply to all these settings, with elementary proofs and very intuitive interpretations. Specifically, we introduce two complexity measures, one which gives lower bounds on classical communication, and one for quantum communication. These measures can be expressed as convex optimization problems. We show that the dual formulations have a striking interpretation, since they coincide with maximum violations of Bell and Tsirelson inequalities. The dual expressions are closely related to the winning probability of XOR games. Despite their apparent simplicity, these lower bounds subsume many known communication complexity lower bound methods, most notably the recent lower bounds of Linial and Shraibman for the special case of Boolean functions. We show that as in the case of Boolean functions, the gap between the quantum and classical lower bounds is at most linear in the size of the support of the distribution, and does not depend on the size of the inputs. This translates into a bound on the gap between maximal Bell and Tsirelson inequality violations, which was previously known only for the case of distributions with Boolean outcomes and uniform marginals. It also allows us to show that for some distributions, information theoretic methods are necessary to prove strong lower bounds. ~~~ Finally, we give an exponential upper bound on quantum and classical communication complexity in the simultaneous messages model, for any non-signaling distribution. One consequence of this is a simple proof that any quantum distribution can be approximated with a constant number of bits of communication.

Quantum Information and Computation•Jul 1, 2011•11 citations

The communication complexity of functions with large outputs

Lila Fontes, Sophie Laplante, Mathieu Laurière +1 more

We study the two-party communication complexity of functions with large outputs, and show that the communication complexity can greatly vary depending on what output model is considered. We study a variety of output models, ranging from the open model, in which an external observer can compute the outcome, to the XOR model, in which the outcome of the protocol should be the bitwise XOR of the players' local outputs. This model is inspired by XOR games, which are widely studied two-player quantum games. We focus on the question of error-reduction in these new output models. For functions of output size k, applying standard error reduction techniques in the XOR model would introduce an additional cost linear in k. We show that no dependency on k is necessary. Similarly, standard randomness removal techniques, incur a multiplicative cost of $2^k$ in the XOR model. We show how to reduce this factor to O(k). In addition, we prove analogous error reduction and randomness removal results in the other models, separate all models from each other, and show that some natural problems, including Set Intersection and Find the First Difference, separate the models when the Hamming weights of their inputs is bounded. Finally, we show how to use the rank lower bound technique for our weak output models.

arXiv:2304.00391•Apr 1, 2023•0 citations

Correlation in Hard Distributions in Communication Complexity

Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck

We study the effect that the amount of correlation in a bipartite distribution has on the communication complexity of a problem under that distribution. We introduce a new family of complexity measures that interpolates between the two previously studied extreme cases: the (standard) randomised communication complexity and the case of distributional complexity under product distributions. We give a tight characterisation of the randomised complexity of Disjointness under distributions with mutual information $k$, showing that it is $Θ(\sqrt{n(k+1)})$ for all $0\leq k\leq n$. This smoothly interpolates between the lower bounds of Babai, Frankl and Simon for the product distribution case ($k=0$), and the bound of Razborov for the randomised case. The upper bounds improve and generalise what was known for product distributions, and imply that any tight bound for Disjointness needs $Ω(n)$ bits of mutual information in the corresponding distribution. We study the same question in the distributional quantum setting, and show a lower bound of $Ω((n(k+1))^{1/4})$, and an upper bound, matching up to a logarithmic factor. We show that there are total Boolean functions $f_d$ on $2n$ inputs that have distributional communication complexity $O(\log n)$ under all distributions of information up to $o(n)$, while the (interactive) distributional complexity maximised over all distributions is $Θ(\log d)$ for $6n\leq d\leq 2^{n/100}$. We show that in the setting of one-way communication under product distributions, the dependence of communication cost on the allowed error $ε$ is multiplicative in $\log(1/ε)$ -- the previous upper bounds had the dependence of more than $1/ε$.

arXiv:1508.05189•Leibniz international proceedings in informatics•Jan 1, 2015•1 citation

Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace

Chengu Wang

We prove that the randomized communication complexity of Vector-in-Subspace in $\mathbb R^n$ with error at most $1/3$ is $Θ(\sqrt n)$. Alice holds a unit vector $u$ and Bob holds an $n/2$-dimensional subspace $H$; they must distinguish $u\in H$ from $u\in H^\perp$. An exact one-way quantum protocol uses $O(\log n)$ qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's $O(\sqrt n)$ upper bound, improves the $Ω(n^{1/3})$ lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's $Ω(\sqrt n)$ result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.

cs.CCCross-listedarXiv:2610.30052•Oct 22, 2026•0 citations

The Communication Complexity of Approximating Matrix Rank

Alexander A. Sherstov, Andrey A. Storozhenko

We fully determine the communication complexity of approximating matrix rank, over any finite field F. We study the most general version of this problem, where$0\leqslant r < R\leqslant n$are given integers and Alice and Bob need to determine whether their respective matrices$A, B\in \mathbb{F}^{n\times n}$satisfy rk$(A+B)=r$versus rk$(A+B)=R$. We show that this problem has commu-nication cost$\Omega(r^{2}\log\vert \mathbb{F}\vert)$, which is optimal. Our lower bound holds even for quantum protocols and even for error probability$\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-r/3})$, which too is optimal because this problem has a two-bit classical protocol with error$\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-\Theta(r)})$. Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integers$r$and$R$, with no implication for the approximation of matrix rank. We also settle an analogous question for subspaces, where Alice has a subspace$S$, Bob has a subspace$T$) and they need to approximate the dimension of the subspace$S+T$generated by$S$and$T$(equivalently, approximate the dimension of$S\cap T$). As an application, we obtain an$\Omega(n^{2}\log\vert \mathbb{F}\vert)/k$memory lower bound for any streaming algorithm with$k$passes that approximates the rank of an input matrix$M\in \mathbb{F}^{n\times n}$within a factor of$\sqrt{2}-\delta$, for any$\delta > 0$. Our result is an exponential improvement in$k$over previous work.

arXiv:2410.20094•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•1 citation

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•3 citations
We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions ppp and qqq over domains XXX and YYY, respectively. Their goal is to estimate [ \mathbb{E}_{x \sim p,, y \sim q}[f(x, y)] ] to within additive error ε\varepsilonε for a bounded function fff, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of fff and the error parameter ε\varepsilonε. The random sampling approach -- estimating the mean by averaging fff over O(1/ε2)O(1/\varepsilon^2)O(1/ε2) random samples -- requires O(R(f)/ε2)O(R(f)/\varepsilon^2)O(R(f)/ε2) total communication, where R(f)R(f)R(f) is the randomized communication complexity of fff. We design a new debiasing protocol which improves the dependence on 1/ε1/\varepsilon1/ε to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.
We study a model of communication complexity that encompasses many well-studied problems, including classical and quantum communication complexity, the complexity of simulating distributions arising from bipartite measurements of shared quantum states, and XOR games. In this model, Alice gets an input xxx, Bob gets an input yyy, and their goal is to each produce an output a,ba,ba,b distributed according to some pre-specified joint distribution p(a,b∣x,y)p(a,b|x,y)p(a,b∣x,y). Our results apply to any non-signaling distribution, that is, those where Alice's marginal distribution does not depend on Bob's input, and vice versa.~~~By taking a geometric view of the non-signaling distributions, we introduce a simple new technique based on affine combinations of lower-complexity distributions, and we give the first general technique to apply to all these settings, with elementary proofs and very intuitive interpretations. Specifically, we introduce two complexity measures, one which gives lower bounds on classical communication, and one for quantum communication. These measures can be expressed as convex optimization problems. We show that the dual formulations have a striking interpretation, since they coincide with maximum violations of Bell and Tsirelson inequalities. The dual expressions are closely related to the winning probability of XOR games. Despite their apparent simplicity, these lower bounds subsume many known communication complexity lower bound methods, most notably the recent lower bounds of Linial and Shraibman for the special case of Boolean functions. We show that as in the case of Boolean functions, the gap between the quantum and classical lower bounds is at most linear in the size of the support of the distribution, and does not depend on the size of the inputs. This translates into a bound on the gap between maximal Bell and Tsirelson inequality violations, which was previously known only for the case of distributions with Boolean outcomes and uniform marginals. It also allows us to show that for some distributions, information theoretic methods are necessary to prove strong lower bounds. ~~~ Finally, we give an exponential upper bound on quantum and classical communication complexity in the simultaneous messages model, for any non-signaling distribution. One consequence of this is a simple proof that any quantum distribution can be approximated with a constant number of bits of communication.
We study the two-party communication complexity of functions with large outputs, and show that the communication complexity can greatly vary depending on what output model is considered. We study a variety of output models, ranging from the open model, in which an external observer can compute the outcome, to the XOR model, in which the outcome of the protocol should be the bitwise XOR of the players' local outputs. This model is inspired by XOR games, which are widely studied two-player quantum games. We focus on the question of error-reduction in these new output models. For functions of output size k, applying standard error reduction techniques in the XOR model would introduce an additional cost linear in k. We show that no dependency on k is necessary. Similarly, standard randomness removal techniques, incur a multiplicative cost of 2k2^k2k in the XOR model. We show how to reduce this factor to O(k). In addition, we prove analogous error reduction and randomness removal results in the other models, separate all models from each other, and show that some natural problems, including Set Intersection and Find the First Difference, separate the models when the Hamming weights of their inputs is bounded. Finally, we show how to use the rank lower bound technique for our weak output models.
We study the effect that the amount of correlation in a bipartite distribution has on the communication complexity of a problem under that distribution. We introduce a new family of complexity measures that interpolates between the two previously studied extreme cases: the (standard) randomised communication complexity and the case of distributional complexity under product distributions. We give a tight characterisation of the randomised complexity of Disjointness under distributions with mutual information kkk, showing that it is Θ(n(k+1))Θ(\sqrt{n(k+1)})Θ(n(k+1)​) for all 0≤k≤n0\leq k\leq n0≤k≤n. This smoothly interpolates between the lower bounds of Babai, Frankl and Simon for the product distribution case (k=0k=0k=0), and the bound of Razborov for the randomised case. The upper bounds improve and generalise what was known for product distributions, and imply that any tight bound for Disjointness needs Ω(n)Ω(n)Ω(n) bits of mutual information in the corresponding distribution. We study the same question in the distributional quantum setting, and show a lower bound of Ω((n(k+1))1/4)Ω((n(k+1))^{1/4})Ω((n(k+1))1/4), and an upper bound, matching up to a logarithmic factor. We show that there are total Boolean functions fdf_dfd​ on 2n2n2n inputs that have distributional communication complexity O(log⁡n)O(\log n)O(logn) under all distributions of information up to o(n)o(n)o(n), while the (interactive) distributional complexity maximised over all distributions is Θ(log⁡d)Θ(\log d)Θ(logd) for 6n≤d≤2n/1006n\leq d\leq 2^{n/100}6n≤d≤2n/100. We show that in the setting of one-way communication under product distributions, the dependence of communication cost on the allowed error εεε is multiplicative in log⁡(1/ε)\log(1/ε)log(1/ε) -- the previous upper bounds had the dependence of more than 1/ε1/ε1/ε.
We prove that the randomized communication complexity of Vector-in-Subspace in Rn\mathbb R^nRn with error at most 1/31/31/3 is Θ(n)Θ(\sqrt n)Θ(n​). Alice holds a unit vector uuu and Bob holds an n/2n/2n/2-dimensional subspace HHH; they must distinguish u∈Hu\in Hu∈H from u∈H⊥u\in H^\perpu∈H⊥. An exact one-way quantum protocol uses O(log⁡n)O(\log n)O(logn) qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's O(n)O(\sqrt n)O(n​) upper bound, improves the Ω(n1/3)Ω(n^{1/3})Ω(n1/3) lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's Ω(n)Ω(\sqrt n)Ω(n​) result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.
We fully determine the communication complexity of approximating matrix rank, over any finite field F. We study the most general version of this problem, where0⩽r<R⩽n0\leqslant r < R\leqslant n0⩽r<R⩽nare given integers and Alice and Bob need to determine whether their respective matricesA,B∈Fn×nA, B\in \mathbb{F}^{n\times n}A,B∈Fn×nsatisfy rk(A+B)=r(A+B)=r(A+B)=rversus rk(A+B)=R(A+B)=R(A+B)=R. We show that this problem has commu-nication costΩ(r2log⁡∣F∣)\Omega(r^{2}\log\vert \mathbb{F}\vert)Ω(r2log∣F∣), which is optimal. Our lower bound holds even for quantum protocols and even for error probability12(1−∣F∣−r/3)\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-r/3})21​(1−∣F∣−r/3), which too is optimal because this problem has a two-bit classical protocol with error12(1−∣F∣−Θ(r))\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-\Theta(r)})21​(1−∣F∣−Θ(r)). Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integersrrrandRRR, with no implication for the approximation of matrix rank. We also settle an analogous question for subspaces, where Alice has a subspaceSSS, Bob has a subspaceTTT) and they need to approximate the dimension of the subspaceS+TS+TS+Tgenerated bySSSandTTT(equivalently, approximate the dimension ofS∩TS\cap TS∩T). As an application, we obtain anΩ(n2log⁡∣F∣)/k\Omega(n^{2}\log\vert \mathbb{F}\vert)/kΩ(n2log∣F∣)/kmemory lower bound for any streaming algorithm withkkkpasses that approximates the rank of an input matrixM∈Fn×nM\in \mathbb{F}^{n\times n}M∈Fn×nwithin a factor of2−δ\sqrt{2}-\delta2​−δ, for anyδ>0\delta > 0δ>0. Our result is an exponential improvement inkkkover previous work.
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.