Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-152 | 12th November 2011 13:28

The communication complexity of addition


Authors: Emanuele Viola
Publication: 12th November 2011 13:28
Downloads: 2958


Suppose each of $k \le n^{o(1)}$ players holds an $n$-bit number $x_i$ in its hand. The players wish to determine if $\sum_{i \le k} x_i = s$. We give a public-coin protocol with error $1\%$ and communication $O(k \lg k)$. The communication bound is independent of $n$, and for $k \ge 3$ improves on the $O(k \log n)$ bound by Nisan (Bolyai Soc.~Math.~Studies; 1993).


Our protocol also applies to addition modulo $m$. In this case we give a matching (public-coin) $\Omega(k \lg k)$ lower bound for various $m$. We also obtain some lower bounds over the integers, including $\Omega(k \lg \lg k)$ for protocols that are one-way, like ours.


We give a protocol to determine if $\sum x_i > s$ with error $1\%$ and communication $O(k \lg k) \lg n$. For $k \ge 3$ this improves on Nisan's $O(k \lg^2 n)$ bound. A similar improvement holds for computing degree-$(k-1)$ polynomial-threshold functions in the number-on-forehead model.


We give a (public-coin, $2$-player, tight) $\Omega(\lg n)$ lower bound to determine if $x_1 > x_2$. This improves on the $\Omega(\sqrt{\lg n})$ bound by
Smirnov (1988).


As an application, we show that polynomial-size $\mathrm{AC^0}$ circuits augmented with $O(1)$ threshold (or symmetric) gates cannot compute cryptographic pseudorandom functions, extending the result about $\mathrm{AC^0}$ by Linial, Mansour, and Nisan (J.~ACM; 1993).

ISSN 1433-8092 | Imprint