×

Interactive information complexity. (English) Zbl 1330.68067

Summary: The primary goal of this paper is to define and study the interactive information complexity of functions. Let \(f(x,y)\) be a function, and suppose Alice is given \(x\) and Bob is given \(y\). Informally, the interactive information complexity \(\mathsf{IC}(f)\) of \(f\) is the least amount of information Alice and Bob need to reveal to each other to compute \(f\). Previously, information complexity has been defined with respect to a prior distribution on the input pairs \((x,y)\). Our first goal is to give a definition that is independent of the prior distribution. We show that several possible definitions are essentially equivalent. We establish some basic properties of the interactive information complexity \(\mathsf{IC}(f)\). In particular, we show that \(\mathsf{IC}(f)\) is equal to the amortized (randomized) communication complexity of \(f\). We also show a direct sum theorem for \(\mathsf{IC}(f)\) and give the first general connection between information complexity and (nonamortized) communication complexity. This connection implies that a nontrivial exchange of information is required when solving problems that have nontrivial communication complexity. We explore the information complexity of two specific problems: Equality and Disjointness. We show that only a constant amount of information needs to be exchanged when solving equality with no errors, while solving disjointness with a constant error probability requires the parties to reveal a linear amount of information to each other.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
94A17 Measures of information, entropy
94A29 Source coding
Full Text: DOI

References:

[1] F. Ablayev, {\it Lower bounds for one-way probabilistic communication complexity and their application to space complexity}, Theoret. Comput. Sci., 157 (1996), pp. 139-159. · Zbl 0871.68009
[2] B. Barak, M. Braverman, X. Chen, and A. Rao, {\it How to compress interactive communication}, in Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, ACM, 2010. · Zbl 1293.68116
[3] R. Bar-Yehuda, B. Chor, E. Kushilevitz, and A. Orlitsky, {\it Privacy, additional information and communication}, IEEE Trans. Inform. Theory, 39 (1993), pp. 1930-1943. · Zbl 0806.94001
[4] Z. Bar-Yossef, T. S. Jayram, R. Kumar, and D. Sivakumar, {\it An information statistics approach to data stream and communication complexity}, J. Comput. System Sci., 68 (2004), pp. 702-732. · Zbl 1074.68022
[5] R. Beigel and J. Tarui, {\it On ACC}, in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, 1991, pp. 783-792.
[6] M. Ben-Or, S. Goldwasser, and A. Wigderson, {\it Completeness theorems for non-cryptographic fault-tolerant distributed computation}, in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, 1988, pp. 1-10.
[7] M. Braverman, A. Garg, Y. K. Ko, J. Mao, and D. Touchette, {\it Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness}, preprint, arXiv preprint arXiv:1505.03110, 2015. · Zbl 1408.68062
[8] M. Braverman, A. Garg, D. Pankratov, and O. Weinstein, {\it From information to exact communication}, in Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing (STOC), ACM, 2013, pp. 151-160. · Zbl 1293.68160
[9] M. Braverman, A. Garg, D. Pankratov, and O. Weinstein, {\it Information lower bounds via self-reducibility}, in Computer Science–Theory and Applications, Springer, 2013, pp. 183-194. · Zbl 1345.68153
[10] M. Braverman and A. Rao, {\it Information equals amortized communication}, IEEE Trans. Inform. Theory, 60 (2014), pp. 6058-6069. · Zbl 1360.94124
[11] M. Braverman, A. Rao, R. Raz, and A. Yehudayoff, {\it Pseudorandom generators for regular branching programs}, in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, 2010, pp. 40-47. · Zbl 1301.68192
[12] M. Braverman, A. Rao, O. Weinstein, and A. Yehudayoff, {\it Direct products in communication complexity}, Electronic Colloquium on Computational Complexity (ECCC), 19 (2012),TR12-143.
[13] M. Braverman, A. Rao, O. Weinstein, and A. Yehudayoff, {\it Direct product via round-preserving compression}, Electronic Colloquium on Computational Complexity (ECCC), 20 (2013), TR13-035. · Zbl 1336.68086
[14] M. Braverman and J. Schneider, {\it Information Complexity Is Computable}, preprint, CoRR, abs/1502.02971, 2015.
[15] M. Braverman and O. Weinstein, {\it A discrepancy lower bound for information complexity}, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer, 2012, pp. 459-470. · Zbl 1372.68113
[16] M. Braverman and O. Weinstein, {\it An interactive information odometer with applications}, Electronic Colloquium on Computational Complexity (ECCC), 21 (2014), TR14-047.
[17] H. Buhrman, H. Klauck, N. K. Vereshchagin, and P. M. B. Vitányi, {\it Individual communication complexity}, J. Comput. System Sci., 73 (2007), pp. 973-985. · Zbl 1121.68057
[18] H. Buhrman, M. Koucký, and N. K. Vereshchagin, {\it Randomised individual communication complexity}, in Proceedings of the 23rd Annual IEEE Conference on Computational Complexity (CCC), IEEE, 2008, pp. 321-331. · Zbl 1191.68004
[19] A. Chakrabarti and O. Regev, {\it An optimal lower bound on the communication complexity of gap-Hamming-distance}, in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), ACM, 2011, pp. 51-60. · Zbl 1288.90005
[20] A. Chakrabarti, Y. Shi, A. Wirth, and A. Yao, {\it Informational complexity and the direct sum problem for simultaneous message complexity}, in Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), B. Werner, ed., IEEE Computer Society, Los Alamitos, CA, 2001, pp. 270-278.
[21] A. Chattopadhyay and A. Ada, {\it Multiparty communication complexity of disjointness}, Electronic Colloquium on Computational Complexity (ECCC), 15 (2008), TR08-002.
[22] T. M. Cover and J. A. Thomas, {\it Elements of Information Theory}, Wiley Ser. Telecom., J. Wiley and Sons, New York, 1991. · Zbl 0762.94001
[23] M. Dietzfelbinger and H. Wunderlich, {\it A characterization of average case communication complexity}, Inform. Process. Lett., 101 (2007), pp. 245-249. · Zbl 1184.68251
[24] T. Feder, E. Kushilevitz, M. Naor, and N. Nisan, {\it Amortized communication complexity}, SIAM J. Comput., 24 (1995), pp. 736-750. · Zbl 0830.68070
[25] L. Fontes, R. Jain, I. Kerenidis, M. Lauriere, S. Laplante, and J. Roland, {\it Relative discrepancy does not separate information and communication complexity}, Electronic Colloquium on Computational Complexity (ECCC), 2015, TR15-028. · Zbl 1440.68090
[26] A. Ganor, G. Kol, and R. Raz, {\it Exponential separation of information and communication}, in Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, 2014, pp. 176-185. · Zbl 1377.68079
[27] A. Ganor, G. Kol, and R. Raz, {\it Exponential separation of communication and external information}, Electronic Colloquium on Computational Complexity (ECCC), 22 (2015), TR15-088. · Zbl 1377.68079
[28] A. Ganor, G. Kol, and R. Raz, {\it Exponential separation of information and communication for boolean functions}, in Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), ACM, 2015, pp. 557-566. · Zbl 1321.68311
[29] P. Harsha, R. Jain, D. A. McAllester, and J. Radhakrishnan, {\it The communication complexity of correlation}, in Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC), IEEE, 2007, pp. 10-23. · Zbl 1366.94020
[30] J. H\aastad and M. Goldmann, {\it On the power of small-depth threshold circuits}, in Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, 1990, pp. 610-618. · Zbl 0774.68060
[31] R. Jain, {\it New strong direct product results in communication complexity}, Electronic Colloquium on Computational Complexity (ECCC), 18 (2011), TR11-024.
[32] R. Jain and H. Klauck, {\it New results in the simultaneous message passing model via information theoretic techniques}, in Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC), IEEE, 2009, pp. 369-378.
[33] R. Jain and H. Klauck, {\it The partition bound for classical communication complexity and query complexity}, in Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC), IEEE, 2010, pp. 247-258.
[34] R. Jain, H. Klauck, and S. Zhang, {\it Depth-independent lower bounds on the communication complexity of read-once boolean formulas}, in COCOON, 2010, pp. 54-59. · Zbl 1286.68195
[35] R. Jain, A. Pereszlényi, and P. Yao, {\it A Direct Product Theorem for Bounded-Round Public-Coin Randomized Communication Complexity}, preprint, CoRR, abs/1201.1666, 2012. · Zbl 1353.68085
[36] R. Jain, J. Radhakrishnan, and P. Sen, {\it Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states}, in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, 2002, pp. 429-438.
[37] R. Jain, J. Radhakrishnan, and P. Sen, {\it A direct sum theorem in communication complexity via message compression}, in Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP), J. C. M. Baeten, J. K. Lenstra, J. Parrow, and G. J. Woeginger, eds., Lecture Notes in Comput. Sci. 2719, Springer, 2003, pp. 300-315. · Zbl 1039.68048
[38] R. Jain, J. Radhakrishnan, and P. Sen, {\it A lower bound for the bounded round quantum communication complexity of set disjointness}, in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003), IEEE, 2003, pp. 220-229.
[39] R. Jain, J. Radhakrishnan, and P. Sen, {\it Prior entanglement, message compression and privacy in quantum communication}, in Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC), IEEE, 2005, pp. 285-296.
[40] R. Jain, J. Radhakrishnan, and P. Sen, {\it A property of quantum relative entropy with an application to privacy in quantum communication}, J. ACM, 56 (2009), 33. · Zbl 1325.81034
[41] R. Jain, P. Sen, and J. Radhakrishnan, {\it Optimal Direct Sum and Privacy Trade-Off Results for Quantum and Classical Communication Complexity}, preprint, arXiv, arXiv:0807.1267, 2008.
[42] R. Jain and P. Yao, {\it A Strong Direct Product Theorem in Terms of the Smooth Rectangle Bound}, preprint, CoRR, abs/1209.0263, 2012.
[43] T. S. Jayram, S. Kopparty, and P. Raghavendra, {\it On the communication complexity of read-once \(ac^0\) formulae}, in Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC), IEEE, 2009, pp. 329-340.
[44] B. Kalyanasundaram and G. Schnitger, {\it The probabilistic communication complexity of set intersection}, SIAM J. Discrete Math., 5 (1992), pp. 545-557. · Zbl 0760.68040
[45] I. Kerenidis, S. Laplante, V. Lerays, J. Roland, and D. Xiao, {\it Lower bounds on information complexity via zero-communication protocols and applications}, in Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, 2012, pp. 500-509. · Zbl 1330.68096
[46] B. Klartag and O. Regev, {\it Quantum one-way communication can be exponentially stronger than classical communication}, in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), ACM, 2011, pp. 31-40. · Zbl 1288.68074
[47] H. Klauck, {\it Quantum and approximate privacy}, Theory Comput. Syst., 37 (2004), pp. 221-246. · Zbl 1107.68422
[48] H. Klauck, {\it A strong direct product theorem for disjointness}, in Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), L. J. Schulman, ed., ACM, 2010, pp. 77-86. · Zbl 1293.68146
[49] H. Klauck, A. Nayak, A. Ta-Shma, and D. Zuckerman, {\it Interaction in quantum communication and the complexity of set disjointness}, in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), ACM, 2001, pp. 124-133. · Zbl 1323.68287
[50] E. Kushilevitz and N. Nisan, {\it Communication Complexity}, Cambridge University Press, Cambridge, UK, 1997. · Zbl 0869.68048
[51] T. Lee and A. Shraibman, {\it Disjointness is hard in the multiparty number-on-the-forehead model}, Comput. Complexity, 18 (2009), pp. 309-336. · Zbl 1213.68314
[52] T. Lee, A. Shraibman, and R. Spalek, {\it A direct product theorem for discrepancy}, in Proceedings of the 23rd Annual IEEE Conference on Computational Complexity (CCC), IEEE, 2008, pp. 71-80.
[53] N. Leonardos and M. Saks, {\it Lower bounds on the randomized communication complexity of read-once functions}, Comput. Complexity, 19 (2010), pp. 153-181. · Zbl 1229.68042
[54] N. Ma and P. Ishwar, {\it Some results on distributed source coding for interactive function computation}, IEEE Trans. Inform. Theory, 57 (2011), pp. 6180-6195. · Zbl 1365.94212
[55] A. McGregor, I. Mironov, T. Pitassi, O. Reingold, K. Talwar, and S. Vadhan, {\it The limits of two-party differential privacy}, in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, 2010, pp. 81-90.
[56] M. Molinaro, D. P. Woodruff, and G. Yaroslavtsev, {\it Beating the direct sum theorem in communication complexity with implications for sketching}, in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, SIAM, 2013, pp. 1738-1756. · Zbl 1422.68075
[57] A. V. Nayak, {\it Lower Bounds for Quantum Computation and Communication}, Ph.D. thesis, University of California, Berkeley, 1999.
[58] A. Orlitsky, {\it Worst-case interactive communication. I. Two messages are almost optimal}, IEEE Trans. Inform. Theory, 36 (1990), pp. 1111-1126. · Zbl 0738.94002
[59] A. Orlitsky, {\it Worst-case interactive communication. II. Two messages are not optimal}, IEEE Trans. Inform. Theory, 37 (1991), pp. 995-1005. · Zbl 0738.94003
[60] A. Rao and A. Yehudayoff, {\it Simplified lower bounds on the multiparty communication complexity of disjointness}, in Proceedings of the 30th Annual IEEE Conference on Computational Complexity (CCC), IEEE, 2015, pp. 88-101. · Zbl 1388.68093
[61] A. Razborov, {\it On the distributed complexity of disjointness}, Theoret. Comput. Sci., 106 (1992), pp. 385-390. · Zbl 0787.68055
[62] R. Shaltiel, {\it Towards proving strong direct product theorems}, Comput. Complexity, 12 (2003), pp. 1-22. · Zbl 1084.68542
[63] C. E. Shannon, {\it A mathematical theory of communication}, Bell Syst. Tech. J., 27 (1948), monograph B-1598. · Zbl 1154.94303
[64] A. A. Sherstov, {\it The communication complexity of gap Hamming distance}, Electronic Colloquium on Computational Complexity (ECCC), 18 (2011), TR11-063.
[65] A. A. Sherstov, {\it Strong direct product theorems for quantum communication and query complexity}, in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), ACM, 2011, pp. 41-50. · Zbl 1288.68076
[66] A. A. Sherstov, {\it The multiparty communication complexity of set disjointness}, in Proceedings of the 44th Annual ACM Symposium on Theory of Computing Conference (STOC), ACM, 2012, pp. 525-548. · Zbl 1286.94118
[67] A. A. Sherstov, {\it Communication lower bounds using directional derivatives}, J. ACM, 61 (2014), pp. 34:1-34:71. · Zbl 1321.68289
[68] D. Slepian and J. K. Wolf, {\it Noiseless coding of correlated information sources}, IEEE Trans. Inform. Theory, 19 (1973), pp. 471-480. · Zbl 0259.94008
[69] D. Touchette, {\it Quantum information complexity}, in Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), ACM, 2015, pp. 317-326. · Zbl 1321.94022
[70] T. Vidick, {\it 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}, Electronic Colloquium on Computational Complexity (ECCC), 18 (2011), TR11-051.
[71] J. von Neumann, {\it Zur theorie der gesellschaftsspiele}, Math. Ann., 100 (1928), pp. 295-320. · JFM 54.0543.02
[72] O. Weinstein, {\it Information complexity and the quest for interactive compression}, SIGACT News, 46 (2015), pp. 41-64.
[73] A. C.-C. Yao, {\it Probabilistic computations: Toward a unified measure of complexity}, in Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 1977, pp. 222-227.
[74] A. C.-C. Yao, {\it On ACC and threshold circuits}, in Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, 1990, pp. 619-627.
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.