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