Interactive communication: balanced distributions, correlated files, and average-case complexity

Suppose (X,Y) is a pair of random variables distributed over a support set S. Person P_x knows X, person P_y knows Y, and both know S. Using a predetermined protocol, they exchange binary messages in order for P_y to learn X. P_x may or may not learn Y. Bounds on communication complexity are obtained and used to obtain efficient protocols for the correlated files problem where X and Y are binary strings (files) within a small edit distance from each other. The average number of bits required for P_y to learn X when at most m messages are permitted is also determined