The probabilistic communication complexity of set intersection. (English) Zbl 0760.68040
Summary: 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.
MSC:
68Q30 | Algorithmic information theory (Kolmogorov complexity, etc.) |
05B20 | Combinatorial aspects of matrices (incidence, Hadamard, etc.) |