2026-07-22T03:53:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7598 2024-03-06T10:40:42Z ddc:004 open_access

Communication Complexity of Statistical Distance Watson, Thomas Communication complexity statistical distance 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 +-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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Watson 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.49 urn:nbn:de:0030-drops-75984 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.49 eng https://creativecommons.org/licenses/by/3.0/legalcode