Let x i ,...,x k  be n-bit numbers and T ∈ N. Assume that P 1 ,..., P k  are players such that P, knows all of the numbers except x i . They want to determine if Σ k  i=1  x j  = T by broadcasting as few bits as possible. In [7] an upper bound of O(√n) bits was obtained for the k = 3 case, and a lower bound of ω(1) for k > 3 when T = Θ(2 n ). We obtain (1) for k ≥ 3 an upper bound of k + O((n + logk) 1/([lg(2k-2)]) , (2) for k = 3, T = Θ(2 n ), a lower bound of Ω(log log n), (3) a generalization of the protocol to abelian groups, (4) lower bounds on the multiparty communication complexity of some regular languages, and (5) empirical results for k = 3.
['Richard Beigel', 'William I. Gasarch', 'James Glenn']
The multiparty communication complexity of exact-T : Improved bounds and new problems