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

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