Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR16-170 | 5th January 2018 07:48

#### Communication Complexity of Statistical Distance

Revision #1
Authors: Thomas Watson
Accepted on: 5th January 2018 07:48
Keywords:

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)$.

### Paper:

TR16-170 | 3rd November 2016 05:21

#### Communication Complexity of Statistical Distance

TR16-170
Authors: Thomas Watson
Publication: 3rd November 2016 14:39
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)$.