ECCC-Report TR11-152https://eccc.weizmann.ac.il/report/2011/152Comments and Revisions published for TR11-152en-usSat, 12 Nov 2011 13:28:35 +0200
Paper TR11-152
| The communication complexity of addition |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2011/152Suppose 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).
\medskip
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.
\medskip
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.
\medskip
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).
\medskip
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).
Sat, 12 Nov 2011 13:28:35 +0200https://eccc.weizmann.ac.il/report/2011/152