1 Department of Computer Science, Science and Technology, Aarhus University2 Department of Computer Science - Center for Massive Data Algoritmics, Department of Computer Science, Science and Technology, Aarhus University3 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University4 University of Utah5 Department of Computer Science, Science and Technology, Aarhus University
In this paper we prove lower bounds on randomized multiparty communication complexity, both in the blackboard model (where each message is written on a blackboard for all players to see) and (mainly) in the message-passing model, where messages are sent player-to-player. We introduce a new technique for proving such bounds, called symmetrization, which is natural, intuitive, and often easy to use. For example, for the problem where each of k players gets a bit-vector of length n, and the goal is to compute the coordinate-wise XOR of these vectors, we prove a tight lower bounds of Ω(nk) in the blackboard model. For the same problem with AND instead of XOR, we prove a lower bounds of roughly Ω(nk) in the message-passing model (assuming k ≤ n/3200) and Ω(n log k) in the blackboard model. We also prove lower bounds for bit-wise majority, for a graphconnectivity problem, and for other problems; the technique seems applicable to a wide range of other problems as well. The obtained communication lower bounds imply new lower bounds in the functional monitoring model  (also called the distributed streaming model). All of our lower bounds allow randomized communication protocols with two-sided error. We also use the symmetrization technique to prove several direct-sum-like results for multiparty communication.
Annual a C M - S I a M Symposium on Discrete Algorithms. Proceedings, 2012, Vol 23, p. 486-501
Main Research Area:
ACM-SIAM Symposium on Discrete Algorithms. SODA 2012Symposium on Discrete Algorithms