__
Revision #1 to TR16-170 | 5th January 2018 07:48
__
#### Communication Complexity of Statistical Distance

**Abstract:**
We prove nearly matching upper and lower bounds on the randomized communication complexity of the following problem: Alice and Bob are each given a probability distribution over $n$ elements, and they wish to estimate within $\pm\epsilon$ the statistical (total variation) distance between their distributions. For some range of parameters, there is up to a $\log n$ factor gap between the upper and lower bounds, and we identify a barrier to using information complexity techniques to improve the lower bound in this case. We also prove a side result that we discovered along the way: the randomized communication complexity of $n$-bit Majority composed with $n$-bit Greater-Than is $\Theta(n\log n)$.

__
TR16-170 | 3rd November 2016 05:21
__

#### Communication Complexity of Statistical Distance

**Abstract:**
We prove nearly matching upper and lower bounds on the randomized communication complexity of the following problem: Alice and Bob are each given a probability distribution over $n$ elements, and they wish to estimate within $\pm\epsilon$ the statistical (total variation) distance between their distributions. For some range of parameters, there is up to a $\log n$ factor gap between the upper and lower bounds, and we identify a barrier to using information complexity techniques to improve the lower bound in this case. We also prove a side result that we discovered along the way: the randomized communication complexity of $n$-bit Majority composed with $n$-bit Greater-Than is $\Theta(n\log n)$.