Inner product and set disjointness: beyond logarithmically many parties

Abstract: A basic goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems

f c o l o n ({0, 1}^{n})^{k} o 0, 1

with

k g g l o g n

parties. We study the problems of inner product and set disjointness and determine their randomized communication complexity for every

k g e q l o g n

, showing in both cases that

T h e t a (1 + l c e i l l o g n c e i l / l o g l c e i l 1 + k / l o g n c e i l)

bits are necessary and sufficient. In particular, these problems admit constant-cost protocols if and only if the number of parties is

k g e q n^{e p s i l o n}

for some constant

e p s i l o n > 0.

Recommendations

Cited in

(5)

This page was built for publication: Inner product and set disjointness: beyond logarithmically many parties