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

Brody, Joshua ; Chakrabarti, Amit

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

pdf-format:
22011.BrodyJoshua.Paper.1341.pdf (0.2 MB)

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 =		{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
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

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