ECCC-Report TR13-013https://eccc.weizmann.ac.il/report/2013/013Comments and Revisions published for TR13-013en-usFri, 18 Jan 2013 20:09:47 +0200
Revision 1
| One-Round Multi-Party Communication Complexity of Distinguishing Sums |
Daniel Apon,
Jonathan Katz,
Alex Malozemoff
https://eccc.weizmann.ac.il/report/2013/013#revision1We 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.Fri, 18 Jan 2013 20:09:47 +0200https://eccc.weizmann.ac.il/report/2013/013#revision1
Paper TR13-013
| One-Round Multi-Party Communication Complexity of Distinguishing Sums |
Daniel Apon,
Jonathan Katz,
Alex Malozemoff
https://eccc.weizmann.ac.il/report/2013/013We 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.Fri, 18 Jan 2013 12:58:19 +0200https://eccc.weizmann.ac.il/report/2013/013