Let x_1,...,x_k be n-bit numbers and T ∈ N. Assume that P_1, ..., P_k are players such that P_i knows all of the numbers except x_i. They want to determine if Σ_(j=1)~k x_j = T by broadcasting as few bits as possible. In [7] an upper bound of O(n~(1/2)) 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 + log k)~(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.
展开▼
