TY - GEN

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

AU - Liang, Guanfeng

AU - Vaidya, Nitin

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 -