Inner Product and Set Disjointness: Beyond Logarithmically Many Parties

11/29/2017

∙

by   Vladimir V. Podolskii, et al.

∙

0

∙

share

A basic goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems f({0,1}^n)^k→{0,1} with k≫ n parties. We study the problems of inner product and set disjointness and determine their randomized communication complexity for every k≥ n, showing in both cases that Θ(1+ n/1+k/ n) bits are necessary and sufficient. In particular, these problems admit constant-cost protocols if and only if the number of parties is k≥ n^ϵ for some constant ϵ>0.