TY - GEN

T1 - Multiparty equality function computation in networks with point-to-point links

AU - Liang, Guanfeng

AU - Vaidya, Nitin

N1 - Funding Information:
This research is supported in part by Army Research Office grant W-911-NF-0710287 and National Science Foundation award 1059540. Any opinions, findings, and conclusions or recommendations expressed here are those of the authors and do not necessarily reflect the views of the funding agencies or the U.S. government.

PY - 2011

Y1 - 2011

N2 - In this paper, we study the problem of computing the multiparty equality (MEQ) function: n≥2 nodes, each of which is given an input value from {1,⋯,K}, determine if their inputs are all identical, under the point-to-point communication model. The MEQ function equals to 1 if and only if all n inputs are identical, and 0 otherwise. The communication complexity of the MEQ problem is defined as the minimum number of bits communicated in the worst case. It is easy to show that (n-1)log2 K bits is an upper bound, by constructing a simple algorithm with that cost. In this paper, we demonstrate that communication cost strictly lower than this upper bound can be achieved. We show this by constructing a static protocol that solves the MEQ problem for n=3, K=6, of which the communication cost is strictly lower than the above upper bound (2log2 6 bits). This result is then generalized for large values of n and K.

AB - In this paper, we study the problem of computing the multiparty equality (MEQ) function: n≥2 nodes, each of which is given an input value from {1,⋯,K}, determine if their inputs are all identical, under the point-to-point communication model. The MEQ function equals to 1 if and only if all n inputs are identical, and 0 otherwise. The communication complexity of the MEQ problem is defined as the minimum number of bits communicated in the worst case. It is easy to show that (n-1)log2 K bits is an upper bound, by constructing a simple algorithm with that cost. In this paper, we demonstrate that communication cost strictly lower than this upper bound can be achieved. We show this by constructing a static protocol that solves the MEQ problem for n=3, K=6, of which the communication cost is strictly lower than the above upper bound (2log2 6 bits). This result is then generalized for large values of n and K.

UR - http://www.scopus.com/inward/record.url?scp=79961150122&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79961150122&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-22212-2_23

DO - 10.1007/978-3-642-22212-2_23

M3 - Conference contribution

AN - SCOPUS:79961150122

SN - 9783642222115

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 258

EP - 269

BT - Structural Information and Communication Complexity - 18th International Colloquium, SIROCCO 2011, Proceedings

T2 - 18th Colloquium on Structural Information and Communication Complexity, SIROCCO 2011

Y2 - 26 June 2011 through 29 June 2011

ER -