Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Communication Complexity of Statistical Distance

RSS-Feed




Revision #1
Authors: Thomas Watson
Accepted on: 5th January 2018 07:48
Downloads: 66
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
Downloads: 526
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)$.



ISSN 1433-8092 | Imprint