The Probabilistic Communication Complexity of Set Intersection
Bala Kalyanasundaram, Georg Schintger · SIAM Journal on Discrete Mathematics · 1992
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.