Multiparty Equality Function Computation in Networks with Point-to-Point Links
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 26, 2010
- Accession Number
- ADA555116
Entities
People
- Guanfeng Liang
- Nitin H. Vaidya
Organizations
- University of Illinois Urbana–Champaign