LOWER BOUNDS ON THE MULTIPARTY COMMUNICATION COMPLEXITY

We derive a general technique for obtaining lower bounds on the multip arty communication complexity of boolean functions. We extend the two- party method based on a crossing sequence argument introduced by Yao t o the multiparty communication model. We use our technique to derive o ptimal 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 determi nistic algorithm computing a boolean function f(x(1),..., x(n)) was de rived, namely of the order (k(0)C(0))(k(1)C(1))(2) up to logarithmic f actors, where k(1) and C-1 are the number of processors accessed and t he bits exchanged in a nondeterministic algorithm for f, and k(0) and C-0 are the analogous parameters for the complementary function 1 - f. We show that C-0 less than or equal to n(1 + 2(C1)) and D less than o r equal to n(1 +2(C1)), where D is the number of bits exchanged by a d eterministic algorithm computing f. 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. (C) 1998 Academic Press.