Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > GREATER-THAN:
Reports tagged with greater-than:
TR11-152 | 12th November 2011
Emanuele Viola

Suppose each of $k \le n^{o(1)}$ players holds an $n$-bit number $x_i$ in its hand. The players wish to determine if $\sum_{i \le k} x_i = s$. We give a public-coin protocol with error $1\%$ and communication $O(k \lg k)$. The communication bound is independent of $n$, and for \$k ... more >>>