In my circuit complexity research, I came across the need to find the communication complexity of approximating addition. Specifically, the class of problems I am interested in is parametrized by four numbers $a,b,k,m$, and given these I want to find the $k$-party number-in-hand deterministic communication complexity of the following problem:

Each player is given an $m$-bit number $x_i$ with the guarantee that $\Sigma_ix_i$ is either less than $a$ or greater than $b$ and they must decide which of these two conditions hold (i.e. whether $\Sigma_ix_i$ is less than $a$ or greater than $b$).

The settings of parameters that are most interesting to me are where $b=Ca=Ckl$ ($C$ is just some constant), $m=\Theta(\log a)$, and I want to choose $k$ as large as possible for given values of $l$ so that the complexity remains linear in $l$. That is, I want $k$ to be a function in $l$ that grows as quickly as possible (ideally it would be linear growth) which still results in linear complexity.

So far, I think I can make $k$ at least $\Omega(\frac{l}{\log\log l})$, but I am still a pesky $\log\log l$ factor away from optimal. In fact, my protocol is even symmetric and simultaneous and works by having each player specify the number of bits in their number. Thus, each player outputs a number in the range $[0,m]$, and so each player outputs about $\log m=O(\log\log l)$ bits of communication. In total, this protocol uses $k\log\log l$ bits of communication, allowing us to choose $k\sim \frac{l}{\log\log l}$. Using these players' messages we can then approximate each of their numbers by a factor of two, and thus approximate the sum by a factor of two.

Can we do any better? Are there any lower bounds to the complexity of approximating addition? I found this paper, but it only studies the communication complexity of exactly computing addition, and I haven't been able to reduce that to an approximate calculation. I have a hunch there's some way to make this work, though, since they also get a similar tight $k\log\log k$ lower bound for the exact computation of addition by one-way protocols. Any help, references, tips, or opinions would be greatly appreciated!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.