^{1} Department of Computer Science, Science and Technology, Aarhus University^{2} Department of Computer Science - Center for Massive Data Algoritmics, Department of Computer Science, Science and Technology, Aarhus University^{3} Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University^{4} University of Utah^{5} Department of Computer Science, Science and Technology, Aarhus University

Abstract:

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 [11] (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.

Type:

Conference paper

Language:

English

Published in:

Annual a C M - S I a M Symposium on Discrete Algorithms. Proceedings, 2012, Vol 23, p. 486-501

Main Research Area:

Science/technology

Publication Status:

Published

Review type:

Peer Review

Conference:

ACM-SIAM Symposium on Discrete Algorithms. SODA 2012Symposium on Discrete Algorithms