We study the randomized communication complexity of the equality function in the public-coin model. Although the communication complexity of this function is known to be low in the setting where error probability is constant and a large number of random bits are available to players, the complexity grows if the allowed error probability and the amount of randomness are restricted.

We show that randomized protocols for equality and error correcting codes are essentially the same object. That is, given a protocol for equality, we can construct a code, and vice versa.

We substantially extend one of the directions of this connection: any protocol computing a function with a large fooling set can be converted into an error correcting code. As a corollary, we show that among functions with a fooling set of size $s$, equality on $\log s$ bits has the least randomized communication complexity, regardless of the restrictions on the error probability and the amount of randomness.

Finally, we use the connection to error correcting codes to analyze the randomized communication complexity of equality for varying restrictions on the error probability and the amount of randomness. In most cases, we provide tight upper bounds. We pinpoint the setting in which tight bounds are still unknown.