18
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      One-Round Multi-Party Communication Complexity of Distinguishing Sums

      Preprint
      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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 the {x_i} 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 collections

          Author and article information

          Journal
          2013-01-17
          2013-01-21
          Article
          1301.4269
          00e50fb3-5a87-44d6-8194-3d9853457107

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          cs.CC

          Theoretical computer science
          Theoretical computer science

          Comments

          Comment on this article