Amortized communication complexity of an equality predicate

Vladimir Nikishkin

We study the communication complexity of a direct sum of independent copies of the equality predicate. We prove that the probabilistic communication complexity of this problem is e…