Amortized Communication Complexity of an Equality Predicate
The authors explain the communication complexity of the direct sum of independent copies of the equality predicate. They prove that the probabilistic communication complexity of this problem is equal to O (N); computational complexity of the proposed protocol is polynomial in size of inputs. Their protocol improves the result achieved. Their construction is based on two techniques: Nisan's pseudorandom generator and Smith's string synchronization algorithm. In this paper, they explain amortized communication complexity of the equality predicate. They deal with the classic model of communication complexity with two participants (Alice and Bob), who want to compute some function of the data distributed between the participants.