The Communication Complexity of the Exact-N Problem Revisited

Algebraic Methods in Computational Complexity

计算机科学;物理学;物理学

William Gasarch1 ; James Glenn2 ; Andre Utis3 ; 2 Dept. of Computer Science ; Loyola College in Maryland ; 4501 N. Charles St ; Baltimore ; MD 21210. ; 3 Institute of Author3 ; Department of Author3 Address ZIP ; Town ; Street ; Country ; 4 University of Maryland

Others  :  http://drops.dagstuhl.de/opus/volltexte/2005/102/pdf/04421.GasarchWilliam1.Paper.102.pdf
PID  :  6465

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

If Alice has x, y, Bob has x, z and Carol has y, z can theydetermine 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 .