License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.224
URN: urn:nbn:de:0030-drops-49162
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4916/
Go to the corresponding LIPIcs Volume Portal

Chattopadhyay, Arkadev ; Mukhopadhyay, Sagnik

Tribes Is Hard in the Message Passing Model

pdf-format:
16.pdf (0.7 MB)

Abstract

We consider the point-to-point message passing model of communication in which there are $k$ processors with individual private inputs, each n-bit long. Each processor is located at the node of an underlying undirected graph and has access to private random coins. An edge of the graph is a private channel of communication between its endpoints. The processors have to compute a given function of all their inputs by communicating along these channels. While this model has been widely used in distributed computing, strong lower bounds on the amount of communication needed to compute simple functions have just begun to appear.

In this work, we prove a tight lower bound of \Omega(kn) on the communication needed for computing the Tribes function, when the underlying graph is a star of k+1 nodes that has k leaves with inputs and a center with no input. A lower bound on this topology easily implies comparable bounds for others. Our lower bounds are obtained by building upon the recent information theoretic techniques of Braverman et al. ([4], FOCS'13) and combining it with the earlier work of Jayram, Kumar and Sivakumar ([10], STOC'03). This approach yields information complexity bounds that are of independent interest.

BibTeX - Entry

@InProceedings{chattopadhyay_et_al:LIPIcs:2015:4916,
  author =	{Arkadev Chattopadhyay and Sagnik Mukhopadhyay},
  title =	{{Tribes Is Hard in the Message Passing Model}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{224--237},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4916},
  URN =		{urn:nbn:de:0030-drops-49162},
  doi =		{10.4230/LIPIcs.STACS.2015.224},
  annote =	{Keywords: communication complexity, Tribes, information complexity, direct-sum}
}

Keywords: communication complexity, Tribes, information complexity, direct-sum
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI