Lower Bounds on the Multiparty Communication Complexity

摘要

We derive a general technique for obtaining lower bounds on the multiparty communication complexity of boolean functions. We extend the two-party method based on a crossing sequence argument introduced by Yao to the multiparty communication model. We use our technique to derive optimal lower and upper bounds of some simple boolean functions. Lower bounds for the multiparty model have been a challenge since (D. Dolev and T. Feder,in“Proceedings, 30th IEEE FOCS, 1989,” pp. 428–433), where only an upper bound on the number of bits exchanged by a deterministic algorithm computing a boolean functionf(x1, …, xn) was derived, namely of the order (k0C0)(k1C1)2, up to logarithmic factors, wherek1andC1are the number of processors accessed and the bits exchanged in a nondeterministic algorithm forf, andk0andC0are the analogous parameters for the complementary function 1−f. We show thatC0⩽n(1+2C1) andD⩽n(1+2C1), whereDis the number of bits exchanged by a deterministic algorithm computingf. We also investigate the power of a restricted multiparty communication model in which the coordinator is allowed to send at most one message to each party.