A discrepancy lower bound for information complexity. (English) Zbl 1353.68088
Summary: This paper provides the first general technique for proving information lower bounds on two-party unbounded-rounds communication problems. We show that the discrepancy lower bound, which applies to randomized communication complexity, also applies to information complexity. More precisely, if the discrepancy of a two-party function \(f\) with respect to a distribution \(\mu \) is \(\mathrm{Disc}_\mu f\), then any two party randomized protocol computing \(f\) must reveal at least \(\Omega (\log (1/\mathrm{Disc}_\mu f))\) bits of information to the participants. As a corollary, we obtain that any two-party protocol for computing a random function on \(\{0,1\}^n\times \{0,1\}^n\) must reveal \(\Omega (n)\) bits of information to the participants. In addition, we prove that the discrepancy of the Greater-Than function is \(\Omega (1/\sqrt{n})\), which provides an alternative proof to the recent proof of E. Viola [“The communication complexity of addition”, in: Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 632–651 (2013; doi:10.1137/1.9781611973105.46)] of the \(\Omega (\log n)\) lower bound on the communication complexity of this well-studied function and, combined with our main result, proves the tight \(\Omega (\log n)\) lower bound on its information complexity. The proof of our main result develops a new simulation procedure that may be of an independent interest. In a followup breakthrough work of I. Kerenidis et al. [“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’12. Los Alamitos, CA: IEEE Computer Society. 500–509 (2012; doi:10.1109/FOCS.2012.68)], our simulation procedure served as a building block towards a proof that almost all known lower bound techniques for communication complexity (and not just discrepancy) apply to information complexity as well.
MSC:
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | Asharov, G., Lindell, Y.: A full proof of the BGW protocol for perfectly-secure multiparty computation. IACR Cryptol. ePrint Arch. 2011, 136 (2011) · Zbl 1370.94480 |
| [2] | Barak, B., Braverman, M., Chen, X., Rao, A.: How to compress interactive communication. In: STOC, pp 67-76 (2010) · Zbl 1293.68116 |
| [3] | Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 1-10. ACM (1988) |
| [4] | Braverman, M., Rao, A.: Information equals amortized communication. IEEE Trans. Inf. Theory 60(10), 6058-6069 (2014) · Zbl 1292.94008 · doi:10.1109/TIT.2014.2347282 |
| [5] | Braverman, M.: Interactive information complexity. In: Proceedings of the 44th Symposium on Theory of Computing, STOC ’12, pp 505-524. ACM, New York, NY (2012) · Zbl 1286.94047 |
| [6] | Bar-Yehuda, R., Chor, B., Kushilevitz, E., Orlitsky, A.: Privacy, additional information and communication. IEEE Trans. Inf. Theory 39(6), 1930-1943 (1993) · Zbl 0806.94001 · doi:10.1109/18.265501 |
| [7] | Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D.: An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci. 68(4), 702-732 (2004) · Zbl 1074.68022 · doi:10.1016/j.jcss.2003.11.006 |
| [8] | Chor, B., Kushilevitz, E.: A zero-one law for boolean privacy. In: Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, pp. 62-72. ACM (1989) · Zbl 0717.94009 |
| [9] | Chakrabarti, A., Shi, Y., Wirth, A., Yao, A.: Informational complexity and the direct sum problem for simultaneous message complexity. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 270-278 (2001) · Zbl 1107.68422 |
| [10] | Ganor, A., Kol, G., Raz. R.: Exponential separation of information and communication for boolean functions. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, 14-17 June 2015, pp. 557-566 (2015) · Zbl 1321.68311 |
| [11] | Harsha, P., Jain, R., McAllester, D., Radhakrishnan, J.: The communication complexity of correlation. In: Twenty-Second Annual IEEE Conference on Computational Complexity, 2007 (CCC’07), pp. 10-23. IEEE (2007) · Zbl 1366.94020 |
| [12] | Jain, R.: A strong direct product theorem for two-way public coin communication complexity. Arxiv preprint arXiv:1010.0846 (2010) |
| [13] | Jain, R., Radhakrishnan, J., Sen, P.: Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states. In: Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, pp. 429-438 (2002) · Zbl 1107.68422 |
| [14] | Jain, R., Sen, P., Radhakrishnan, J.: Optimal direct sum and privacy trade-off results for quantum and classical communication complexity. Arxiv preprint arXiv:0807.1267 (2008) · Zbl 1084.68542 |
| [15] | Klauck, H.: Quantum and approximate privacy. Theory Comput. Syst. 37(1), 221-246 (2004) · Zbl 1107.68422 · doi:10.1007/s00224-003-1113-7 |
| [16] | Klauck, H.: A strong direct product theorem for disjointness. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, pp. 77-86. ACM (2010) · Zbl 1293.68146 |
| [17] | Kerenidis, I., Laplante, S., Lerays, V., Roland, J., Xiao, D.: Lower bounds on information complexity via zero-communication protocols and applications. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, 20-23 October 2012, pp. 500-509 (2012) · Zbl 1330.68096 |
| [18] | Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, New York (1997). 96012840 96012840 Eyal Kushilevitz, Noam Nisan · Zbl 0869.68048 · doi:10.1016/S0065-2458(08)60342-3 |
| [19] | Klauck, H., Spalek, R., De Wolf, R.: Quantum and classical strong direct product theorems and optimal time-space tradeoffs. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 12-21. IEEE (2004) · Zbl 1123.68045 |
| [20] | Lee, T., Shraibman, A., Spalek. R.: A direct product theorem for discrepancy. In: 23rd Annual IEEE Conference on Computational Complexity, 2008 (CCC’08), pp. 71-80. IEEE (2008) |
| [21] | Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A.: On data structures and asymmetric communication complexity. In: Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, pp. 103-111. ACM (1995) · Zbl 0968.68507 |
| [22] | Razborov, A.A.: On the distributional complexity of disjointness. Theor. Comput. Sci. 106(2), 385-390 (1992) · Zbl 0787.68055 · doi:10.1016/0304-3975(92)90260-M |
| [23] | Shaltiel, R.: Towards proving strong direct product theorems. Comput. Complex. 12(1), 1-22 (2003) · Zbl 1084.68542 · doi:10.1007/s00037-003-0175-x |
| [24] | Smirnov. D.V.: Shannon’s information methods for lower bounds for probabilistic communication complexity. Master’s thesis, Moscow State University (1988) · Zbl 1074.68022 |
| [25] | Viola, E.: The communication complexity of addition. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, LA, USA, 6-8 January 2013, pp. 632-651 (2013) · Zbl 1422.68076 |
| [26] | Viola, E., Wigderson, A.: Norms, xor lemmas, and lower bounds for polynomials and protocols. Theory Comput. 4(1), 137-168 (2008) · Zbl 1213.68321 · doi:10.4086/toc.2008.v004a007 |
| [27] | Yao, A.C.C.: Some complexity questions related to distributive computing. In: STOC, pp. 209-213 (1979) |
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.
