The Probabilistic Communication Complexity of Set Intersection

Abstract

It is shown that, for inputs of length n, the probabilistic (bounded error) communication complexity of set intersection is $\Theta ( n )$. Since set intersection can be recognized nondeterministically by exchanging $O( \log n )$ bits, the result implies an exponential gap between nondeterminism and probabilism. This gap is the largest possible. The first general technique to analyze the probabilistic communication complexity of sparse languages is also described.