Accession Number:

ADA555116

Title:

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

Descriptive Note:

Technical rept.

Corporate Author:

ILLINOIS UNIV AT URBANA-CHAMPAIGN

Personal Author(s):

Report Date:

2010-10-26

Pagination or Media Count:

12.0

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-AD3,6 problem and introduce an optimal protocol that achieves CsubAD3, 6. This protocol is then used as building blocks for construction of efficient protocols for MEQ-AD3,6h and MEQ-AD3,2k. The problem of finding the communication complexity of the MEQ problem for general values of n and M is still open.

Subject Categories:

  • Operations Research
  • Computer Programming and Software
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE