Article ID Journal Published Year Pages File Type
434577 Theoretical Computer Science 2013 8 Pages PDF
Abstract

We consider an instance of the following problem: Parties P1,…,PkP1,…,Pk each receive an input xixi, and a coordinator (distinct from each of these parties) wishes to compute f(x1,…,xk)f(x1,…,xk) for some predicate f. We are interested in one-round protocols where each party sends a single message to the coordinator; there is no communication between the parties themselves. What is the minimum communication complexity needed to compute f, possibly with bounded error?We prove tight bounds on the one-round communication complexity when f corresponds to the promise problem of distinguishing sums   (namely, determining which of two possible values the {xi}{xi} sum to) or the problem of determining whether the {xi}{xi} sum to a particular value. Similar problems were studied previously by Nisan and in concurrent work by Viola. Our proofs rely on basic theorems from additive combinatorics, but are otherwise elementary.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,