Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-013 | 18th January 2013 20:09

One-Round Multi-Party Communication Complexity of Distinguishing Sums

RSS-Feed




Revision #1
Authors: Daniel Apon, Jonathan Katz, Alex Malozemoff
Accepted on: 18th January 2013 20:09
Downloads: 1016
Keywords: 


Abstract:

We consider an instance of the following problem: Parties $P_1,..., P_k$ each receive an input $x_i$, and a coordinator (distinct from each of these parties) wishes to compute $f(x_1,..., x_k)$ 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 $\{x_i\}$ sum to) or the problem of determining whether they 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.



Changes to previous version:

Fixed typos


Paper:

TR13-013 | 18th January 2013 00:12

One-Round Multi-Party Communication Complexity of Distinguishing Sums


Abstract:

We consider an instance of the following problem: Parties $P_1,..., P_k$ each receive an input $x_i$, and a coordinator (distinct from each of these parties) wishes to compute $f(x_1,..., x_k)$ 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 $\{x_i\}$ sum to) or the problem of determining whether they 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.



ISSN 1433-8092 | Imprint