ECCC-Report TR14-074https://eccc.weizmann.ac.il/report/2014/074Comments and Revisions published for TR14-074en-usFri, 16 May 2014 23:37:26 +0300
Paper TR14-074
| Topology matters in communication |
Arkadev Chattopadhyay,
Jaikumar Radhakrishnan,
Atri Rudra
https://eccc.weizmann.ac.il/report/2014/074We 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).Fri, 16 May 2014 23:37:26 +0300https://eccc.weizmann.ac.il/report/2014/074