Document Open Access Logo

Communication Complexity of Statistical Distance

Author Thomas Watson

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.49.pdf
  • Filesize: 0.51 MB
  • 10 pages

Document Identifiers

Author Details

Thomas Watson

Cite As Get BibTex

Thomas Watson. Communication Complexity of Statistical Distance. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 49:1-49:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.49

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

Subject Classification

Keywords
  • Communication
  • complexity
  • statistical
  • distance

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, and Miklos Santha. Separations in communication complexity using cheat sheets and information complexity. In Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS), pages 555-564. IEEE, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.66.
  2. Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren Smith, and Patrick White. Testing closeness of discrete distributions. Journal of the ACM, 60(1):4, 2013. URL: http://dx.doi.org/10.1145/2432622.2432626.
  3. Andrej Bogdanov, Elchanan Mossel, and Salil Vadhan. The complexity of distinguishing Markov random fields. In Proceedings of the 12th International Workshop on Randomization and Computation (RANDOM), pages 331-342. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-85363-3_27.
  4. Mark Braverman. Interactive information complexity. SIAM Journal on Computing, 44(6):1698-1739, 2015. URL: http://dx.doi.org/10.1137/130938517.
  5. Mark Braverman and Omri Weinstein. An interactive information odometer and applications. In Proceedings of the 47th Symposium on Theory of Computing (STOC), pages 341-350. ACM, 2015. URL: http://dx.doi.org/10.1145/2746539.2746548.
  6. Mark Braverman and Omri Weinstein. A discrepancy lower bound for information complexity. Algorithmica, 76(3):846-864, 2016. URL: http://dx.doi.org/10.1007/s00453-015-0093-8.
  7. Clément Canonne. A survey on distribution testing: Your data is big. But is it blue? Technical Report TR15-063, Electronic Colloquium on Computational Complexity (ECCC), 2015. URL: http://eccc.hpi-web.de/report/2015/063.
  8. Amit Chakrabarti and Oded Regev. An optimal lower bound on the communication complexity of Gap-Hamming-Distance. SIAM Journal on Computing, 41(5):1299-1317, 2012. URL: http://dx.doi.org/10.1137/120861072.
  9. Siu On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant. Optimal algorithms for testing closeness of discrete distributions. In Proceedings of the 25th Symposium on Discrete Algorithms (SODA), pages 1193-1203. ACM-SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.88.
  10. Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan. An approximate L¹-difference algorithm for massive data streams. SIAM Journal on Computing, 32(1):131-151, 2002. URL: http://dx.doi.org/10.1137/S0097539799361701.
  11. Jessica Fong and Martin Strauss. An approximate L^p-difference algorithm for massive data streams. Discrete Mathematics & Theoretical Computer Science, 4(2):301-322, 2001. Google Scholar
  12. Oded Goldreich, Amit Sahai, and Salil Vadhan. Can statistical zero knowledge be made non-interactive? or On the relationship of SZK and NISZK. In Proceedings of the 19th International Cryptology Conference (CRYPTO), pages 467-484. Springer, 1999. URL: http://dx.doi.org/10.1007/3-540-48405-1_30.
  13. Oded Goldreich and Salil Vadhan. Comparing entropies in statistical zero-knowledge with applications to the structure of SZK. In Proceedings of the 14th Conference on Computational Complexity (CCC), pages 54-73. IEEE, 1999. URL: http://dx.doi.org/10.1109/CCC.1999.766262.
  14. Oded Goldreich and Salil Vadhan. On the complexity of computational problems regarding distributions. Studies in Complexity and Cryptography, pages 390-405, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22670-0_27.
  15. Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized communication vs. partition number. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl, 2017. To appear. Google Scholar
  16. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. SIAM Journal on Computing, 45(5):1835-1869, 2016. URL: http://dx.doi.org/10.1137/15M103145X.
  17. Thomas Holenstein. Parallel repetition: Simplification and the no-signaling case. Theory of Computing, 5(1):141-172, 2009. URL: http://dx.doi.org/10.4086/toc.2009.v005a008.
  18. Rahul Jain and Hartmut Klauck. The partition bound for classical communication complexity and query complexity. In Proceedings of the 25th Conference on Computational Complexity (CCC), pages 247-258. IEEE, 2010. URL: http://dx.doi.org/10.1109/CCC.2010.31.
  19. Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, and David Xiao. Lower bounds on information complexity via zero-communication protocols and applications. SIAM Journal on Computing, 44(5):1550-1572, 2015. URL: http://dx.doi.org/10.1137/130928273.
  20. Jon Kleinberg and Éva Tardos. Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields. Journal of the ACM, 49(5):616-639, 2002. URL: http://dx.doi.org/10.1145/585265.585268.
  21. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. Google Scholar
  22. Anup Rao. Parallel repetition in projection games and a concentration bound. SIAM Journal on Computing, 40(6):1871-1891, 2011. URL: http://dx.doi.org/10.1137/080734042.
  23. Ran Raz. A counterexample to strong parallel repetition. SIAM Journal on Computing, 40(3):771-777, 2011. URL: http://dx.doi.org/10.1137/090747270.
  24. Ronitt Rubinfeld. Taming big probability distributions. ACM Crossroads, 19(1):24-28, 2012. URL: http://dx.doi.org/10.1145/2331042.2331052.
  25. Amit Sahai and Salil Vadhan. A complete problem for statistical zero knowledge. Journal of the ACM, 50(2):196-249, 2003. URL: http://dx.doi.org/10.1145/636865.636868.
  26. Alexander Sherstov. The communication complexity of Gap Hamming Distance. Theory of Computing, 8(1):197-208, 2012. URL: http://dx.doi.org/10.4086/toc.2012.v008a008.
  27. Paul Valiant. Testing symmetric properties of distributions. SIAM Journal on Computing, 40(6):1927-1968, 2011. URL: http://dx.doi.org/10.1137/080734066.
  28. Thomas Vidick. 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. Chicago Journal of Theoretical Computer Science, 2012(1):1-12, 2012. URL: http://dx.doi.org/10.4086/cjtcs.2012.001.
  29. Thomas Watson. The complexity of deciding statistical properties of samplable distributions. Theory of Computing, 11:1-34, 2015. URL: http://dx.doi.org/10.4086/toc.2015.v011a001.
  30. Thomas Watson. The complexity of estimating min-entropy. Computational Complexity, 25(1):153-175, 2016. URL: http://dx.doi.org/10.1007/s00037-014-0091-2.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact