Multiparty Equality Function Computation in Networks with Point-to- Point Links

摘要

In this report, we study the communication complexity problem of the multiparty equality function, under the point-to-point communication model. We demonstrate that traditional techniques generalized from two-party communication complexity problem are not sufficient to obtain tight bounds under the point-to-point communication model. We then introduce techniques to transform any MEQ-AD protocol into a equivalent partially ordered iid protocol. These techniques significantly reduce the space of MEQ-AD protocols to study. We then study the MEQ-AD(3,6) problem and introduce an optimal protocol that achieves C(subAD)(3, 6). This protocol is then used as building blocks for construction of efficient protocols for MEQ-AD(3,6(h)) and MEQ-AD(3,2(k)). The problem of finding the communication complexity of the MEQ problem for general values of n and M is still open.