In our paper we construct a new randomized communication protocol for the direct sum of the equality predicate.
Our protocol is computationally effective, i.e., it only requires polynomial computations for Alice and Bob.
Our construction improves the result from [1]} in two respects. First of all, we get a slightly better bound for the probability of error. And, second, our protocol has a “modular” structure; it consist of several independent gadgets, which make the construction more flexible. We hope that the same technique can be applied to other problems of communication complexity.
