Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Communication Complexity of Statistical Distance

Communication Complexity of 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 ε 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 (n log n). http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Communication Complexity of Statistical Distance

Watson, Thomas
ACM Transactions on Computation Theory (TOCT) , Volume 10 (1): 11 – Jan 24, 2018
Download PDF
11 pages

Loading next page...
 
/lp/association-for-computing-machinery/communication-complexity-of-statistical-distance-FwPe5qTy8r
Publisher
Association for Computing Machinery
Copyright
Copyright © 2018 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3170708
Publisher site
See Article on Publisher Site

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 ε 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 (n log n).

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Jan 24, 2018

Keywords: Communication

References

  • Separations in communication complexity using cheat sheets and information complexity
    Anshu, Anurag; Belovs, Aleksandrs; Ben-David, Shalev; Göös, Mika; Jain, Rahul; Kothari, Robin; Lee, Troy; Santha, Miklos
  • An information statistics approach to data stream and communication complexity
    Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D.
  • Testing closeness of discrete distributions
    Batu, Tugkan; Fortnow, Lance; Rubinfeld, Ronitt; Smith, Warren; White, Patrick
  • The complexity of distinguishing Markov random fields
    Bogdanov, Andrej; Mossel, Elchanan; Vadhan, Salil
  • Interactive information complexity
    Braverman, Mark
  • An interactive information odometer and applications
    Braverman, Mark; Weinstein, Omri
  • A discrepancy lower bound for information complexity
    Braverman, Mark; Weinstein, Omri
  • A Survey on Distribution Testing: Your Data is Big
    Canonne, Clément
  • An optimal lower bound on the communication complexity of Gap-Hamming-Distance
    Chakrabarti, Amit; Regev, Oded
  • Optimal algorithms for testing closeness of discrete distributions
    Chan, Siu On; Diakonikolas, Ilias; Valiant, Paul; Valiant, Gregory
  • An approximate L1-difference algorithm for massive data streams
    Feigenbaum, Joan; Kannan, Sampath; Strauss, Martin; Viswanathan, Mahesh
  • An approximate Lp-difference algorithm for massive data streams
    Fong, Jessica; Strauss, Martin
  • Can statistical zero knowledge be made non-interactive? or On the relationship of SZK and NISZK
    Goldreich, Oded; Sahai, Amit; Vadhan, Salil
  • Comparing entropies in statistical zero-knowledge with applications to the structure of SZK
    Goldreich, Oded; Vadhan, Salil
  • On the complexity of computational problems regarding distributions
    Goldreich, Oded; Vadhan, Salil
  • Randomized communication vs
    Göös, Mika; Jayram, T. S.; Pitassi, Toniann; Watson, Thomas
  • Rectangles are nonnegative juntas
    Göös, Mika; Lovett, Shachar; Meka, Raghu; Watson, Thomas; Zuckerman, David
  • Parallel repetition: Simplification and the no-signaling case
    Holenstein, Thomas
  • The partition bound for classical communication complexity and query complexity
    Jain, Rahul; Klauck, Hartmut
  • Lower bounds on information complexity via zero-communication protocols and applications
    Kerenidis, Iordanis; Laplante, Sophie; Lerays, Virginie; Roland, Jérémie; Xiao, David
  • Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields
    Kleinberg, Jon; Tardos, Éva
  • Communication Complexity
    Kushilevitz, Eyal; Nisan, Noam
  • Parallel repetition in projection games and a concentration bound
    Rao, Anup
  • A counterexample to strong parallel repetition
    Raz, Ran
  • Taming big probability distributions
    Rubinfeld, Ronitt
  • A complete problem for statistical zero knowledge
    Sahai, Amit; Vadhan, Salil
  • The communication complexity of Gap Hamming Distance
    Sherstov, Alexander
  • Testing symmetric properties of distributions
    Valiant, Paul
  • A concentration inequality for the overlap of a vector on a large set, with application to the communication complexity of the Gap-Hamming-Distance problem
    Vidick, Thomas
  • The complexity of deciding statistical properties of samplable distributions
    Watson, Thomas
  • The complexity of estimating min-entropy
    Watson, Thomas
  • Communication complexity of statistical distance
    Watson, Thomas