The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems

Let xi,...,xk be n-bit numbers and T∈ℕ. Assume that P1,...,Pk are players such that Pi knows all of the numbers exceptxi. They want to determine if $\sum^{k}_{j=1}{\it x}_{j}$= T by broadcasting as few bits as possible. In [7] an upper bound of $O(\sqrt n )$ bits was obtained for the k=3 case, and a lower bound of ω(1) for k ≥3 when T=Θ(2n). We obtain (1) for k ≥3 an upper bound of $k+O((n+\log k)^{1/(\lfloor{\rm lg(2k-2)}\rfloor)})$, (2) for k=3, T=Θ(2n), a lower bound of Ω(loglogn), (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.