×

Simplified separation of information and communication. (English) Zbl 1412.68060

Summary: We give an example of a boolean function whose information complexity is exponentially smaller than its communication complexity. Such a separation was first demonstrated by A. Ganor et al. [J. ACM 63, No. 5, Paper No. 46, 31 p. (2016; Zbl 1412.68082)]. We give a simpler proof of the same result. In the course of this simplification, we make several new contributions: we introduce a new communication lower-bound technique, the notion of a fooling distribution, which allows us to separate information and communication complexity, and we also give a more direct proof of the information complexity upper bound.
We also prove a generalization of Shearer’s Lemma that may be of independent interest. A version of Shearer’s original lemma bounds the expected mutual information of a subset of random variables with another random variable, when the subset is chosen independently of all the random variables that are involved. Our generalization allows some dependence between the random subset and the random variables involved, and still gives us similar bounds with an appropriate error term.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Citations:

Zbl 1412.68082
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] [1] ZIVBAR-YOSSEF, T. S. JAYRAM, RAVIKUMAR,ANDD. SIVAKUMAR: An information statistics approach to data stream and communication complexity. J. Comput. System Sci., 68(4):702-732, 2004. Conference version inFOCS’02. [doi:10.1016/j.jcss.2003.11.006]2
[2] [2] BOAZBARAK, MARKBRAVERMAN, XICHEN,ANDANUPRAO: How to compress interactive communication. SIAM J. Comput., 42(3):1327-1363, 2013. Conference version inSTOC’10. [doi:10.1137/100811969]2
[3] [3] MARKBRAVERMAN: Interactive information complexity. SIAM J. Comput., 44(6):1698-1739, 2015. Conference version inSTOC’12. [doi:10.1137/130938517]2,3,4,11 · Zbl 1330.68067
[4] [4] MARKBRAVERMAN ANDANKITGARG: Public vs private coin in bounded-round information. In Proc. 41st Internat. Colloq. on Automata, Languages and Programming (ICALP’14), pp. 502-513. · Zbl 1395.68116
[5] [5] MARKBRAVERMANANDANUPRAO:Information equals amortized communication. IEEE Trans. Inform. Theory, 60(10):6058-6069, 2014.Conference version inFOCS’11. [doi:10.1109/TIT.2014.2347282,arXiv:1106.3595]2 · Zbl 1360.94124
[6] [6] MARKBRAVERMAN, ANUPRAO, OMRIWEINSTEIN,ANDAMIRYEHUDAYOFF: Direct products in communication complexity. In Proc. 54th FOCS, pp. 746-755. IEEE Comp. Soc. Press, 2013. [doi:10.1109/FOCS.2013.85]2,6,7
[7] [7] MARKBRAVERMAN ANDOMRIWEINSTEIN: A discrepancy lower bound for information complexity. Algorithmica, 76(3):846-864, 2016. Conference version inAPPROX’12. [doi:10.1007/s00453015-0093-8,arXiv:1112.2000]2,4 · Zbl 1353.68088
[8] [8] AMITCHAKRABARTI, YAOYUNSHI, ANTHONYWIRTH,ANDANDREWCHI-CHIHYAO: Informational complexity and the direct sum problem for simultaneous message complexity. In Proc. 42nd FOCS, pp. 270-278. IEEE Comp. Soc. Press, 2001. [doi:10.1109/SFCS.2001.959901]2
[9] [9] FANR. K. CHUNG, RONALDL. GRAHAM, PETERFRANKL,ANDJAMESB. SHEARER: Some intersection theorems for ordered sets and graphs. J. Combin. Theory Ser. A, 43(1):23-37, 1986. [doi:10.1016/0097-3165(86)90019-1]13,14
[10] [10] THOMASM. COVER ANDJOYA. THOMAS: Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, 2006.6
[11] [11] URIELFEIGE, PRABHAKARRAGHAVAN, DAVIDPELEG,ANDELIUPFAL: Computing with noisy information. SIAM J. Comput., 23(5):1001-1018, 1994. Conference version inSTOC’90. [doi:10.1137/S0097539791195877]10
[12] [12] LILAFONTES, RAHULJAIN, IORDANISKERENIDIS, SOPHIELAPLANTE, MATHIEULAURIÈRE, ANDJÉRÉMIEROLAND: Relative discrepancy does not separate information and communication complexity. ACM Trans. Comput. Theory, 9(1):4:1-4:15, 2016. Conference version inICALP’15. [doi:10.1145/2967605]4,21,22
[13] [13] ANATGANOR, GILLATKOL,ANDRANRAZ:Exponential separation of information and communication.In Proc. 55th FOCS, pp. 176-185. IEEE Comp. Soc. Press, 2014. [doi:10.1109/FOCS.2014.27]3
[14] [14] ANATGANOR, GILLATKOL,ANDRANRAZ:Exponential separation of communication and external information.In Proc. 48th STOC, pp. 977-986. ACM Press, 2016. [doi:10.1145/2897518.2897535]4
[15] [15] ANATGANOR, GILLATKOL,ANDRANRAZ: Exponential separation of information and communication for Boolean functions. J. ACM, 63(5):46:1-46:31, 2016. Conference version inSTOC’15. [doi:10.1145/2907939]3,4,6,7,10,14,19,20,21,22
[16] [16] PRAHLADHHARSHA, RAHULJAIN, DAVIDA. MCALLESTER,ANDJAIKUMARRADHAKRISHNAN: The communication complexity of correlation. IEEE Trans. Inform. Theory, 56(1):438-449, 2010. Conference version inCCC’07. [doi:10.1109/TIT.2009.2034824]2
[17] [17] BALAKALYANASUNDARAM ANDGEORGSCHNITGER: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math., 5(4):545-557, 1992. Conference version in 2nd Structure in Complexity Theory Conf., 1987. [doi:10.1137/0405044]2
[18] [18] IORDANISKERENIDIS, SOPHIELAPLANTE, VIRGINIELERAYS, JÉRÉMIEROLAND,AND DAVIDXIAO: Lower bounds on information complexity via zero-communication protocols and applications. SIAM J. Comput., 44(5):1550-1572, 2015. Conference version inFOCS’12. [doi:10.1137/130928273,arXiv:1204.1505]2
[19] [19] GILLATKOL: Interactive compression for product distributions. In Proc. 48th STOC, pp. 987-998. ACM Press, 2016. [doi:10.1145/2897518.2897537]2 · Zbl 1377.68080
[20] [20] EYALKUSHILEVITZ ANDNOAMNISAN: Communication Complexity. Cambridge University Press, 1997.8
[21] [21] SIVARAMAKRISHNANNATARAJANRAMAMOORTHY ANDANUPRAO: How to compress asymmetric communication. In Proc. 30th Conf. on Computational Complexity (CCC’15), pp. 102-123. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.CCC.2015.102]2
[22] [22] SIVARAMAKRISHNANNATARAJANRAMAMOORTHY ANDMAKRANDSINHA: On the communication complexity of greater-than.In Proc. 53rd Ann. Allerton Conf. on Communication, Control, and Computing (Allerton’15), pp. 442-444. IEEE Comp. Soc. Press, 2015. [doi:10.1109/ALLERTON.2015.7447037]4
[23] [23] JAIKUMARRADHAKRISHNAN: Entropy and counting. In Computational Mathematics, Modelling and Algorithms, pp. 146-168. Narosa Publishers, 2003. Available fromauthor’s home page.13,14
[24] [24] ANUPRAO ANDMAKRANDSINHA: Simplified separation of information and communication. Electron. Colloq. on Comput. Complexity (ECCC), 2015. [ECCC:TR15-057]
[25] [25] ALEXANDERA. RAZBOROV: On the distributional complexity of disjointness. Theoret. Comput. Sci., 106(2):385-390, 1992. Conference version inICALP’90. [doi:10.1016/0304-3975(92)90260M]2 · Zbl 0787.68055
[26] [26] CLAUDEE. SHANNON: A mathematical theory of communication. The Bell System Technical Journal, 27(3):379-423, 1948. [doi:10.1002/j.1538-7305.1948.tb01338.x]2 · Zbl 1154.94303
[27] [27] ALEXANDERA. SHERSTOV:Compressing interactive communication under product distributions.SIAM J. Comput., 47(2):367-419, 2018.Conference version inFOCS’16. [doi:10.1137/16M109380X]2 · Zbl 1391.68033
[28] [28] EMANUELEVIOLA: The communication complexity of addition. Combinatorica, 35(6):703-747, 2015. Conference version inSODA’13. [doi:10.1007/s00493-014-3078-3 · Zbl 1374.68228
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.