The Round Complexity of Small Set Intersection

David P. Woodruff, Grigory Yaroslavtsev

The set disjointness problem is one of the most fundamental and well-studied problems in communication complexity. In this problem Alice and Bob hold sets $S,T\subseteq [n]$, res…