Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-074 | 14th May 2014 16:34

Topology matters in communication



We provide the first communication lower bounds that are sensitive to the network topology for computing natural and simple functions by point to point message passing protocols for the `Number in Hand' model. All previous lower bounds were either for the broadcast model or assumed full connectivity of the network. As a special case, we obtain bounds of the form $\Omega(k^2 n)$ on the randomized communication complexity of many simple functions for a broad class of networks having $k$ distributed nodes and each holding an $n$-bit input string. The best previous bounds were of the form $\Omega(kn)$. The main tool that we use for deriving our bounds is a new connection with the theory of metric embeddings. This enables us to prove a variety of results that include the following: A distributed XOR lemma; a tight bound (discarding poly-log factors) on the randomized complexity of Element Distinctness that answers a question of Phillips, Verbin and Zhang (SODA'12) and new lower bounds for composed functions that were also left open in the work of Phillips et al. Finally, these bounds yield new topology-dependent bounds for several natural graph problems considered by Woodruff and Zhang (DISC'13).

ISSN 1433-8092 | Imprint