1 Search Results for "Glenn, James"


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-dev.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}
}
  • Refine by Author
  • 1 Gasarch, William
  • 1 Glenn, James
  • 1 Utis, Andre

  • Refine by Classification

  • Refine by Keyword
  • 1 Arithmetic Sequences
  • 1 Communication Complexity
  • 1 Exact-N problem

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2005

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