کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434577 689760 2013 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
One-round multi-party communication complexity of distinguishing sums
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
One-round multi-party communication complexity of distinguishing sums
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 501, 27 August 2013, Pages 101–108
نویسندگان
, , ,