The communication complexity of addition (Q519955)

From the summary: Suppose each of \(k\leq n^{o(1)}\) players holds an \(n\)-bit number \(x_i\) in its hand. The players wish to determine if \(\sum_{i\leq k}x_i =s\). We give a public-coin protocol with error 1\% and communication \(O(k \log k)\). The communication bound is independent of \(n\), and for \(k\geq 3\) improves on the \(O(k \log n)\) bound by \textit{N. Nisan} [in: Combinatorics, Paul Erdős is eighty. Vol. 1. Budapest: János Bolyai Mathematical Society. Bolyai Society Mathematical Studies. 301--315 (1993; Zbl 0790.94028)]. Our protocol also applies to addition modulo \(m\). In this case we give a matching (public-coin) \(\Omega (k \log k)\) lower bound for various \(m\). We also obtain some lower bounds over the integers, including \(\Omega (k \log \log 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\log k)\log n\). For \(k\geq 3\) this improves on Nisan's \(O(k \log^{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 (\log n)\) lower bound to determine if \(x_1>x_2\). This improves on the \(\Omega(\sqrt{\log n})\) bound by Smirnov (1988). Troy Lee informed us in January 2013 that an \(\Omega(\log n)\) lower bound may also be obtained by combining a result in learning theory by \textit{J. Forster} et al. [Mach. Learn. 51, No. 3, 263--281 (2003; Zbl 1026.68112)] with a result by \textit{N. Linial} and \textit{A. Shraibman} [Comb. Probab. Comput. 18, No. 1--2, 227--245 (2009; Zbl 1202.68314)]. 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 \textit{N. Linial} et al. [J. Assoc. Comput. Mach. 40, No. 3, 607--620 (1993; Zbl 0781.94006)].