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 -