DETERMINISTIC COMMUNICATION COMPLEXITY OF SET INTERSECTION

In this paper the communication complexity C(m(n)) of the cardinality of set intersection, m(n) say, will be determined up to one bit: n + [ log,(n + 1)] - 1 less than or equal to C(m(n)) less than or equal to n + [log(2)(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(O, y) = f(x, O) = O for all possible x, y. Furthermore, using Kraft' s inequality for prefix codes, it is possible to find a communication protocol, which for n = 2(t), t greater than or equal to 2, assumes th e lower bound. The upper bound is assumed for n = 2(t) - 1, t epsilon N.