Abstract
Sparse (or small) set disjointness is the communication game where Alice and Bob are given each a set of size k in a larger universe and they are to find out if the two sets are disjoint. The randomized communication complexity of this problem is was found by Hastad and Wigderson ('97, '07): it is O(k). In this joint result with Mert Saglam we improve their O(log k) round protocol to a log* k round protocol of the same complexity and find an optimal tradeoff between the length and the number of rounds: to solve the sparse set disjointness problem in an r
A major advantage of our protocols is that we find the intersection of the two sets exactly and do not only decide whether it is empty. For the lower bound we use a new isoperimetric inequality.