Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Brody, Joshua; Chakrabarti, Amit http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-13415
URL:

;

Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound

pdf-format:


Abstract

We study the one-way number-on-the-forehead (NOF) communication complexity of the $k$-layer pointer jumping problem with $n$ vertices per layer. This classic problem, which has connections to many aspects of complexity theory, has seen a recent burst of research activity, seemingly preparing the ground for an $Omega(n)$ lower bound, for constant $k$. Our first result is a surprising sublinear --- i.e., $o(n)$ --- upper bound for the problem that holds for $k ge 3$, dashing hopes for such a lower bound. A closer look at the protocol achieving the upper bound shows that all but one of the players involved are collapsing, i.e., their messages depend only on the composition of the layers ahead of them. We consider protocols for the pointer jumping problem where all players are collapsing. Our second result shows that a strong $n - O(log n)$ lower bound does hold in this case. Our third result is another upper bound showing that nontrivial protocols for (a non-Boolean version of) pointer jumping are possible even when all players are collapsing. Our lower bound result uses a novel proof technique, different from those of earlier lower bounds that had an information-theoretic flavor. We hope this is useful in further study of the problem.

BibTeX - Entry

@InProceedings{brody_et_al:LIPIcs:2008:1341,
  author =	{Joshua Brody and Amit Chakrabarti},
  title =	{{Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{145--165},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1341},
  URN =		{urn:nbn:de:0030-drops-13415},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1341},
  annote =	{Keywords: Communication complexity, pointer jumping, number on the forehead}
}

Keywords: Communication complexity, pointer jumping, number on the forehead
Seminar: 25th International Symposium on Theoretical Aspects of Computer Science
Issue date: 2008
Date of publication: 2008


DROPS-Home | Fulltext Search | Imprint Published by LZI