arXiv:2410.20094 · Annual Symposium on Foundations of Computer Science

The Communication Complexity of Approximating Matrix Rank

Alexander A. Sherstov, Andrey A. Storozhenko

Published Oct 27, 2024• 1 citation

Abstract

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.

DOI: 10.1109/focs61266.2024.00035

Related papers

Communication Complexity of Integer Matrix Singularity

Chengu Wang

cs.CCCross-listedarXiv:2610.33521Oct 27, 20260 citations

Randomized Communication Complexity for Linear Algebra Problems over Finite Fields

Xiaoming Sun, Chengu Wang

Leibniz international proceedings in informaticsJan 1, 201212 citations

Some Bounds on Communication Complexity of Gap Hamming Distance

Alexander Kozachinskiy

arXiv:1511.08854Nov 27, 20151 citation

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

Chengu Wang

cs.CCCross-listedarXiv:2610.30052Oct 22, 20260 citations

Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems

Andris Ambainis, William I. Gasarch, Aravind Srinivasan +1 more

ACM Transactions on Computation TheoryJun 26, 20156 citations

The communication complexity of distributed estimation

Parikshit Gopalan, Raghu Meka, Prasad Raghavendra +2 more

arXiv:2511.21015Nov 26, 20250 citations

arXiv:2410.20094 · Annual Symposium on Foundations of Computer Science

The Communication Complexity of Approximating Matrix Rank

Alexander A. Sherstov, Andrey A. Storozhenko

Published Oct 27, 2024• 1 citation

arXiv HTML PDF

Abstract

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.

DOI: 10.1109/focs61266.2024.00035

Related papers

Communication Complexity of Integer Matrix Singularity

Chengu Wang

Alice and Bob hold complementary halves of the columns of an $n\times n$ matrix of $k$ -bit integers and decide whether it is singular over $\mathbb Q$ . Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold $n\times n$ matrices $A,B$ of $k$ -bit integers and test the singularity of $A+B$ over $\mathbb Q$ . We prove a bounded-error quantum lower bound $Ω(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})$ and a randomized upper bound $O(n^2\min\{k,\log(k+\log n)\})$ . The bounds match at $Θ(n^2\log(nk))$ for $k\ge n\log n$ . The lower bound holds even under the promise of rank $n-1$ versus $n$ . Its proof combines an integer witness with a local digit encoding, while the upper-bound protocol lifts modular kernel relations using short messages. Bitwise sharing changes how the communication complexity depends on the entry bit length $k$ . If Alice and Bob instead hold $n\times n$ matrices $A,B$ of $k$ -bit integers and test whether their entrywise bitwise XOR $A\oplus B$ is singular over $\mathbb Q$ , we prove a quantum lower bound $Ω(n^2k)$ , matching the trivial upper bound. This lower bound holds even under the promise of rank $n-1$ versus $n$ . Our proof uses a dense weighted equation and a signed Fourier witness whose exceptional dyadic frequencies can be removed at small variation cost.Alice and Bob hold complementary halves of the columns of an $n\times n$ matrix of $k$-bit integers and decide whether it is singular over $\mathbb Q$. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold $n\times n$ matrices $A,B$ of $k$-bit integers and test the singularity of $A+B$ over $\mathbb Q$. We prove a bounded-error quantum lower bound $Ω(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})$ and a randomized upper bound $O(n^2\min\{k,\log(k+\log n)\})$. The bounds match at $Θ(n^2\log(nk))$ for $k\ge n\log n$. The lower bound holds even under the promise of rank $n-1$ versus $n$. Its proof combines an integer witness with a local digit encoding, while the upper-bound protocol lifts modular kernel relations using short messages. Bitwise sharing changes how the communication complexity depends on the entry bit length $k$. If Alice and Bob instead hold $n\times n$ matrices $A,B$ of $k$-bit integers and test whether their entrywise bitwise XOR $A\oplus B$ is singular over $\mathbb Q$, we prove a quantum lower bound $Ω(n^2k)$, matching the trivial upper bound. This lower bound holds even under the promise of rank $n-1$ versus $n$. Our proof uses a dense weighted equation and a signed Fourier witness whose exceptional dyadic frequencies can be removed at small variation cost.

cs.CCCross-listedarXiv:2610.33521Oct 27, 20260 citations

Randomized Communication Complexity for Linear Algebra Problems over Finite Fields

Xiaoming Sun, Chengu Wang

Finding the singularity of a matrix is a basic problem in linear algebra. Chu and Schnitger [SC95] first considered this problem in the communication complexity model, in which Alice holds the first half of the matrix and Bob holds the other half. They proved that the deterministic communication complexity is Omega(n^2 log p) for an n by n matrix over the finite field F_p. Then, Clarkson and Woodruff [CW09] introduced the singularity problem to the streaming model. They proposed a randomized one pass streaming algorithm that uses O(k^2 log n) space to decide if the rank of a matrix is k, and proved an Omega(k^2) lower bound for randomized one-way protocols in the communication complexity model. We prove that the randomized/quantum communication complexity of the singularity problem over F_p is Omega(n^2 log p), which implies the same space lower bound for randomized streaming algorithms, even for a constant number of passes. The proof uses the framework by Lee and Shraibman [LS09], but we choose Fourier coefficients as the witness for the dual approximate norm of the communication matrix. Moreover, we use Fourier analysis to show the same randomized/quantum lower bound when deciding if the determinant of a non-singular matrix is a or b for non-zero a and b.Finding the singularity of a matrix is a basic problem in linear algebra. Chu and Schnitger [SC95] first considered this problem in the communication complexity model, in which Alice holds the first half of the matrix and Bob holds the other half. They proved that the deterministic communication complexity is Omega(n^2 log p) for an n by n matrix over the finite field F_p. Then, Clarkson and Woodruff [CW09] introduced the singularity problem to the streaming model. They proposed a randomized one pass streaming algorithm that uses O(k^2 log n) space to decide if the rank of a matrix is k, and proved an Omega(k^2) lower bound for randomized one-way protocols in the communication complexity model. We prove that the randomized/quantum communication complexity of the singularity problem over F_p is Omega(n^2 log p), which implies the same space lower bound for randomized streaming algorithms, even for a constant number of passes. The proof uses the framework by Lee and Shraibman [LS09], but we choose Fourier coefficients as the witness for the dual approximate norm of the communication matrix. Moreover, we use Fourier analysis to show the same randomized/quantum lower bound when deciding if the determinant of a non-singular matrix is a or b for non-zero a and b.

Leibniz international proceedings in informaticsJan 1, 201212 citations

Some Bounds on Communication Complexity of Gap Hamming Distance

Alexander Kozachinskiy

In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem ( $\mathsf{GHD}^n_{L, U}$ ): Alice and Bob are given binary string of length $n$ and they are guaranteed that Hamming distance between their inputs is either $\le L$ or $\ge U$ for some $L < U$ . They have to output 0, if the first inequality holds, and 1, if the second inequality holds. In this paper we study the communication complexity of $\mathsf{GHD}^n_{L, U}$ for probabilistic protocols with one-sided error and for deterministic protocols. Our first result is a protocol which communicates $O\left(\left(\frac{s}{U}\right)^\frac{1}{3} \cdot n\log n\right)$ bits and has one-sided error probability $e^{-s}$ provided $s \ge \frac{(L + \frac{10}{n})^3}{U^2}$ . Our second result is about deterministic communication complexity of $\mathsf{GHD}^n_{0,\, t}$ . Surprisingly, it can be computed with logarithmic precision: $\mathrm{D}(\mathsf{GHD}^n_{0,\, t}) = n - \log_2 V_2\left(n, \left\lfloor\frac{t}{2}\right\rfloor\right) + O(\log n),$ where $V_2(n, r)$ denotes the size of Hamming ball of radius $r$ . As an application of this result for every $c < 2$ we prove a $Ω\left(\frac{n(2 - c)^2}{p}\right)$ lower bound on the space complexity of any $c$ -approximate deterministic $p$ -pass streaming algorithm for computing the number of distinct elements in a data stream of length $n$ with tokens drawn from the universe $U = \{1, 2, \ldots, n\}$ . Previously that lower bound was known for $c < \frac{3}{2}$ and for $c < 2$ but with larger $|U|$ .In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem ($\mathsf{GHD}^n_{L, U}$): Alice and Bob are given binary string of length $n$ and they are guaranteed that Hamming distance between their inputs is either $\le L$ or $\ge U$ for some $L < U$. They have to output 0, if the first inequality holds, and 1, if the second inequality holds. In this paper we study the communication complexity of $\mathsf{GHD}^n_{L, U}$ for probabilistic protocols with one-sided error and for deterministic protocols. Our first result is a protocol which communicates $O\left(\left(\frac{s}{U}\right)^\frac{1}{3} \cdot n\log n\right)$ bits and has one-sided error probability $e^{-s}$ provided $s \ge \frac{(L + \frac{10}{n})^3}{U^2}$. Our second result is about deterministic communication complexity of $\mathsf{GHD}^n_{0,\, t}$. Surprisingly, it can be computed with logarithmic precision: $$\mathrm{D}(\mathsf{GHD}^n_{0,\, t}) = n - \log_2 V_2\left(n, \left\lfloor\frac{t}{2}\right\rfloor\right) + O(\log n),$$ where $V_2(n, r)$ denotes the size of Hamming ball of radius $r$. As an application of this result for every $c < 2$ we prove a $Ω\left(\frac{n(2 - c)^2}{p}\right)$ lower bound on the space complexity of any $c$-approximate deterministic $p$-pass streaming algorithm for computing the number of distinct elements in a data stream of length $n$ with tokens drawn from the universe $U = \{1, 2, \ldots, n\}$. Previously that lower bound was known for $c < \frac{3}{2}$ and for $c < 2$ but with larger $|U|$.

arXiv:1511.08854Nov 27, 20151 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.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.30052Oct 22, 20260 citations

Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems

Andris Ambainis, William I. Gasarch, Aravind Srinivasan +1 more

Alice and Bob want to know if two strings of length n are almost equal. That is, do the strings differ on at most a bits? Let 0 ⩽ a ⩽ n − 1. We show (1) any deterministic protocol—as well as any error-free quantum protocol ( C * version)—for this problem requires at least n − 2 bits of communication, and (2) a lower bound of n /2 − 1 for error-free Q * quantum protocols. We also show the same results for determining if two strings differ in exactly a bits. Our results are obtained by lower-bounding the ranks of the appropriate matrices.Alice and Bob want to know if two strings of length n are almost equal. That is, do the strings differ on at most a bits? Let 0 ⩽ a ⩽ n − 1. We show (1) any deterministic protocol—as well as any error-free quantum protocol ( C * version)—for this problem requires at least n − 2 bits of communication, and (2) a lower bound of n /2 − 1 for error-free Q * quantum protocols. We also show the same results for determining if two strings differ in exactly a bits. Our results are obtained by lower-bounding the ranks of the appropriate matrices.

ACM Transactions on Computation TheoryJun 26, 20156 citations

The communication complexity of distributed estimation

Parikshit Gopalan, Raghu Meka, Prasad Raghavendra +2 more

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.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.

arXiv:2511.21015Nov 26, 20250 citations

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.

Alice and Bob hold complementary halves of the columns of an

n\times n

matrix of

k

-bit integers and decide whether it is singular over

\mathbb Q

. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold

n\times n

matrices

A,B

k

-bit integers and test the singularity of

A+B

over

\mathbb Q

. We prove a bounded-error quantum lower bound

Ω(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})

and a randomized upper bound

O(n^2\min\{k,\log(k+\log n)\})

. The bounds match at

Θ(n^2\log(nk))

for

k\ge n\log n

. The lower bound holds even under the promise of rank

n-1

versus

n

. Its proof combines an integer witness with a local digit encoding, while the upper-bound protocol lifts modular kernel relations using short messages. Bitwise sharing changes how the communication complexity depends on the entry bit length

k

. If Alice and Bob instead hold

n\times n

matrices

A,B

k

-bit integers and test whether their entrywise bitwise XOR

A\oplus B

is singular over

\mathbb Q

, we prove a quantum lower bound

Ω(n^2k)

, matching the trivial upper bound. This lower bound holds even under the promise of rank

n-1

versus

n

. Our proof uses a dense weighted equation and a signed Fourier witness whose exceptional dyadic frequencies can be removed at small variation cost.

In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem (

\mathsf{GHD}^n_{L, U}

): Alice and Bob are given binary string of length

n

and they are guaranteed that Hamming distance between their inputs is either

\le L

\ge U

for some

L < U

. They have to output 0, if the first inequality holds, and 1, if the second inequality holds. In this paper we study the communication complexity of

\mathsf{GHD}^n_{L, U}

for probabilistic protocols with one-sided error and for deterministic protocols. Our first result is a protocol which communicates

O\left(\left(\frac{s}{U}\right)^\frac{1}{3} \cdot n\log n\right)

bits and has one-sided error probability

e^{-s}

provided

s \ge \frac{(L + \frac{10}{n})^3}{U^2}

. Our second result is about deterministic communication complexity of

\mathsf{GHD}^n_{0,\, t}

. Surprisingly, it can be computed with logarithmic precision:

\mathrm{D}(\mathsf{GHD}^n_{0,\, t}) = n - \log_2 V_2\left(n, \left\lfloor\frac{t}{2}\right\rfloor\right) + O(\log n),

where

V_2(n, r)

denotes the size of Hamming ball of radius

r

. As an application of this result for every

c < 2

we prove a

Ω\left(\frac{n(2 - c)^2}{p}\right)

lower bound on the space complexity of any

c

-approximate deterministic

p

-pass streaming algorithm for computing the number of distinct elements in a data stream of length

n

with tokens drawn from the universe

U = \{1, 2, \ldots, n\}

. Previously that lower bound was known for

c < \frac{3}{2}

and for

c < 2

but with larger

|U|

We prove that the randomized communication complexity of Vector-in-Subspace in

\mathbb R^n

with error at most

1/3

Θ(\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.

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.