Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy
Authors:
- Jeff M. PhillipsJPJeff M. Phillips
- Elad VerbinEVElad Verbin
- Qin ZhangQZQin Zhang
Preprint
Abstract
In this paper we prove lower bounds on randomized multiparty communication complexity, both in the \emph{blackboard model} (where each message is written on a blackboard for all players to see) and (mainly) in the \emph{message-passing model}, where messages are sent player-to-player. We introduce a new technique for proving such bounds, called \emph{symmetrization}, which is natural, intuitive, and relatively easy to use in comparison to other techniques for proving such bounds such as the \emph{icost method} \cite{BYJKS02}. 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 $\Omega(nk)$ in the blackboard model. For the same problem with AND instead of XOR, we prove a lower bounds of roughly $\Omega(nk)$ in the message-passing model (assuming $k \le n/3200$) and $\Omega(n \log k)$ in the blackboard model. We also prove lower bounds for bit-wise majority, for a graph-connectivity 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 \emph{functional monitoring model} \cite{CMY08} (also called the \emph{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.
Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Optimal Tracking of Distributed Heavy Hitters and QuantilesAlgorithmica, 2011
- Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams2009
- Functional Monitoring without Monotonicity2009
- Approximate distributed top-k queriesDistributed Computing, 2008
- Practical Methods for Shape Fitting and Kinetic Data Structures using CoresetsAlgorithmica, 2007
- Faster core-set constructions and data-stream algorithms in fixed dimensionsComputational Geometry, 2006
- Geometric Approximation via Coresets2005
- Finding (Recently) Frequent Items in Distributed Data Streams2005
- Lower Bounds on the Multiparty Communication ComplexityJournal of Computer and System Sciences, 1998
- Finding repeated elementsScience of Computer Programming, 1982