License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.04421.6
URN: urn:nbn:de:0030-drops-1026
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/102/
Go to the corresponding Portal

Gasarch, William ; Glenn, James ; Utis, Andre

The communication complexity of the Exact-N Problem revisited

pdf-format:
04421.GasarchWilliam1.Paper.102.pdf (0.3 MB)

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:DagSemProc.04421.6,
  author =	{Gasarch, William and Glenn, James and Utis, Andre},
  title =	{{The communication complexity of the Exact-N Problem revisited}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4421},
  editor =	{Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2005/102},
  URN =		{urn:nbn:de:0030-drops-1026},
  doi =		{10.4230/DagSemProc.04421.6},
  annote =	{Keywords: Communication Complexity , Exact-N problem , Arithmetic Sequences}
}

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

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