Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy

TY - GEN

T1 - Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy

AU - Phillips, Jeff

AU - Verbin, Elad

AU - Zhang, Qin

N1 - Title of the vol.:Title of the vol.: 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, January 17-19, 2012 in Kyoto, Japan ISBN: CD - 978-1-611972-11-5 ISSN: CD 2160-1445 ISSN: Online 1557-9468

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

M3 - Conference article

SN - 1071-9040

VL - 23

SP - 486

EP - 501

JO - The Annual A C M - S I A M Symposium on Discrete Algorithms. Proceedings

JF - The Annual A C M - S I A M Symposium on Discrete Algorithms. Proceedings

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

Y2 - 17 January 2012 through 19 January 2012

ER -