Search Results

Documents authored by Utis, Andre


Document
The communication complexity of the Exact-N Problem revisited

Authors: William Gasarch, James Glenn, and Andre Utis

Published in: Dagstuhl Seminar Proceedings, Volume 4421, Algebraic Methods in Computational Complexity (2005)


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.

Cite as

William Gasarch, James Glenn, and Andre Utis. The communication complexity of the Exact-N Problem revisited. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 4421, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.04421.6},
  URN =		{urn:nbn:de:0030-drops-1026},
  doi =		{10.4230/DagSemProc.04421.6},
  annote =	{Keywords: Communication Complexity , Exact-N problem , Arithmetic Sequences}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail