License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-1026
URL: http://drops.dagstuhl.de/opus/volltexte/2005/102/

Gasarch, William ; Glenn, James ; Utis, Andre

The communication complexity of the Exact-N Problem revisited

pdf-format:
Dokument 1.pdf (278 KB)


Abstract

If Alice has x, y, Bob has x, z and Carol has y, z can they determine if x+y+z=N? They can if (say) Alice broadcasts x to Bob and Carol; can they do better? Chandra, Furst, and Lipton studied this problem and showed sublinear upper bounds. They also had matching (up to an additive constant) lower bounds. We give an exposition of their result with some attention to what happens for particular values of N.

BibTeX - Entry

@InProceedings{gasarch_et_al:DSP:2005:102,
  author =	{William Gasarch and James Glenn and Andre Utis},
  title =	{The communication complexity of the Exact-N Problem revisited},
  booktitle =	{Algebraic Methods in Computational Complexity},
  year =	{2005},
  editor =	{Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  number =	{04421},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2005/102},
  annote =	{Keywords: Communication Complexity , Exact-N problem , Arithmetic Sequences}
}

Keywords: Communication Complexity , Exact-N problem , Arithmetic Sequences
Seminar: 04421 - Algebraic Methods in Computational Complexity
Issue date: 2005
Date of publication: 24.03.2005


DROPS-Home | Fulltext Search | Imprint Published by LZI