Communication complexity of statistical distance. (English) Zbl 1467.68056
Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 49, 10 p. (2017).
Summary: 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 \varepsilon\) 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)\).
For the entire collection see [Zbl 1372.68012].
For the entire collection see [Zbl 1372.68012].
MSC:
| 68Q11 | Communication complexity, information complexity |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
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 Found-ations of Computer Science (FOCS), pages 555-564. IEEE, 2016. doi:10.1109/FOCS.2016. 66. · doi: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. doi:10.1145/ 2432622.2432626. · Zbl 1281.68227 · doi:10.1145/2432622.2432626 |
| [3] | Andrej Bogdanov, Elchanan Mossel, and Salil Vadhan. The complexity of distinguish-ing Markov random fields. In Proceedings of the 12th International Workshop on Ran-domization and Computation (RANDOM), pages 331-342. Springer, 2008. doi:10.1007/ 978-3-540-85363-3_27. 49:9 · Zbl 1159.68042 · doi:10.1007/978-3-540-85363-3_27 |
| [4] | Mark Braverman. Interactive information complexity. SIAM Journal on Computing, 44(6):1698-1739, 2015. doi:10.1137/130938517. · Zbl 1330.68067 · doi:10.1137/130938517 |
| [5] | Mark Braverman and Omri Weinstein. An interactive information odometer and applic-ations. In Proceedings of the 47th Symposium on Theory of Computing (STOC), pages 341-350. ACM, 2015. doi:10.1145/2746539.2746548. · Zbl 1321.68260 · doi:10.1145/2746539.2746548 |
| [6] | Mark Braverman and Omri Weinstein. A discrepancy lower bound for information com-plexity. Algorithmica, 76(3):846-864, 2016. doi:10.1007/s00453-015-0093-8. · Zbl 1353.68088 · doi: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. · Zbl 1441.68281 |
| [8] | Amit Chakrabarti and Oded Regev. An optimal lower bound on the communication com-plexity of Gap-Hamming-Distance. SIAM Journal on Computing, 41(5):1299-1317, 2012. doi:10.1137/120861072. · Zbl 1259.68087 · doi: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. doi:10.1137/1.9781611973402. 88. · Zbl 1421.68184 · doi:10.1137/1.9781611973402.88 |
| [10] | Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan. An ap-proximate L 1 -difference algorithm for massive data streams. SIAM Journal on Computing, 32(1):131-151, 2002. doi:10.1137/S0097539799361701. · Zbl 1029.68157 · doi: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. · Zbl 0990.68195 |
| [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. doi:10. 1007/3-540-48405-1_30. · Zbl 0942.68046 · doi: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 Computa-tional Complexity (CCC), pages 54-73. IEEE, 1999. doi:10.1109/CCC.1999.766262. · doi: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. doi:10.1007/ 978-3-642-22670-0_27. · Zbl 1343.68115 · doi:10.1007/978-3-642-22670-0_27 |
| [15] | Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized commu-nication vs. partition number. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl, 2017. To appear. · Zbl 1441.68050 |
| [16] | Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rect-angles are nonnegative juntas. SIAM Journal on Computing, 45(5):1835-1869, 2016. doi:10.1137/15M103145X. · Zbl 1353.68130 · doi:10.1137/15M103145X |
| [17] | Thomas Holenstein. Parallel repetition: Simplification and the no-signaling case. Theory of Computing, 5(1):141-172, 2009. doi:10.4086/toc.2009.v005a008. · Zbl 1213.68297 · doi:10.4086/toc.2009.v005a008 |
| [18] | Rahul Jain and Hartmut Klauck. The partition bound for classical communication com-plexity and query complexity. In Proceedings of the 25th Conference on Computational Complexity (CCC), pages 247-258. IEEE, 2010. doi:10.1109/CCC.2010.31. · doi: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 applica-tions. SIAM Journal on Computing, 44(5):1550-1572, 2015. doi:10.1137/130928273. · Zbl 1330.68096 · doi: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. doi:10.1145/585265.585268. · Zbl 1326.68336 · doi:10.1145/585265.585268 |
| [21] | Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. · Zbl 0869.68048 |
| [22] | Anup Rao. Parallel repetition in projection games and a concentration bound. SIAM Journal on Computing, 40(6):1871-1891, 2011. doi:10.1137/080734042. · Zbl 1235.68078 · doi:10.1137/080734042 |
| [23] | Ran Raz. A counterexample to strong parallel repetition. SIAM Journal on Computing, 40(3):771-777, 2011. doi:10.1137/090747270. · Zbl 1234.68141 · doi:10.1137/090747270 |
| [24] | Ronitt Rubinfeld. Taming big probability distributions. ACM Crossroads, 19(1):24-28, 2012. doi:10.1145/2331042.2331052. · doi: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. doi:10.1145/636865.636868. · Zbl 1326.68165 · doi:10.1145/636865.636868 |
| [26] | Alexander Sherstov. The communication complexity of Gap Hamming Distance. Theory of Computing, 8(1):197-208, 2012. doi:10.4086/toc.2012.v008a008. · Zbl 1253.68158 · doi:10.4086/toc.2012.v008a008 |
| [27] | Paul Valiant. Testing symmetric properties of distributions. SIAM Journal on Computing, 40(6):1927-1968, 2011. doi:10.1137/080734066. · Zbl 1233.62112 · doi: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. doi:10.4086/cjtcs. 2012.001. · Zbl 1286.68364 · doi:10.4086/cjtcs.2012.001 |
| [29] | Thomas Watson. The complexity of deciding statistical properties of samplable distribu-tions. Theory of Computing, 11:1-34, 2015. doi:10.4086/toc.2015.v011a001. · Zbl 1336.68108 · doi:10.4086/toc.2015.v011a001 |
| [30] | Thomas Watson. The complexity of estimating min-entropy. Computational Complexity, 25(1):153-175, 2016. doi:10.1007/s00037-014-0091-2. · Zbl 1336.68109 · doi:10.1007/s00037-014-0091-2 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
