Deterministic communication complexity of set intersection Original Research Article

In this paper the communication complexity C(mn) of the cardinality of set intersection, mn say, will be determined up to one bit: n + ⌈log2(n + 1)⌉ − 1 ⩽ C(mn) ⩽ n + ⌈log2(n + 1)⌉. The proof for the lower bound can also be applied to a larger class of “sum-type” functions sharing the property that f(0,y) = f(x,0) = 0 for all possible x,y. Furthermore, using Kraftʹs inequality for prefix codes, it is possible to find a communication protocol, which for n = 2t, t ⩾ 2, assumes the lower bound. The upper bound is assumed for n = 2t − 1, t ϵ N.