DagSemProc.04421.6.pdf
- Filesize: 277 kB
- 14 pages
Document
The communication complexity of the Exact-N Problem revisited
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 4421
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2005-03-24
Cite AsGet BibTex
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)
https://doi.org/10.4230/DagSemProc.04421.6
https://doi.org/10.4230/DagSemProc.04421.6
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.
Keywords
- Communication Complexity
- Exact-N problem
- Arithmetic Sequences
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads