Simplified Separation of Information and Communication

by Anup Rao and Makrand Sinha

Theory of Computing, Volume 14(20), pp. 1-29, 2018

Bibliography with links to cited articles

[1]   Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar: An information statistics approach to data stream and communication complexity. J. Comput. System Sci., 68(4):702–732, 2004. Conference version in FOCS’02. [doi:10.1016/j.jcss.2003.11.006]

[2]   Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao: How to compress interactive communication. SIAM J. Comput., 42(3):1327–1363, 2013. Conference version in STOC’10. [doi:10.1137/100811969]

[3]   Mark Braverman: Interactive information complexity. SIAM J. Comput., 44(6):1698–1739, 2015. Conference version in STOC’12. [doi:10.1137/130938517]

[4]   Mark Braverman and Ankit Garg: Public vs private coin in bounded-round information. In Proc. 41st Internat. Colloq. on Automata, Languages and Programming (ICALP’14), pp. 502–513. Springer, 2014. Full version ECCC TR13-130. [doi:10.1007/978-3-662-43948-7_42]

[5]   Mark Braverman and Anup Rao: Information equals amortized communication. IEEE Trans. Inform. Theory, 60(10):6058–6069, 2014. Conference version in FOCS’11. [doi:10.1109/TIT.2014.2347282, arXiv:1106.3595]

[6]   Mark Braverman, Anup Rao, Omri Weinstein, and Amir Yehudayoff: Direct products in communication complexity. In Proc. 54th FOCS, pp. 746–755. IEEE Comp. Soc. Press, 2013. [doi:10.1109/FOCS.2013.85]

[7]   Mark Braverman and Omri Weinstein: A discrepancy lower bound for information complexity. Algorithmica, 76(3):846–864, 2016. Conference version in APPROX’12. [doi:10.1007/s00453-015-0093-8, arXiv:1112.2000]

[8]   Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew Chi-Chih Yao: 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]

[9]   Fan R. K. Chung, Ronald L. Graham, Peter Frankl, and James B. 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]

[10]   Thomas M. Cover and Joy A. Thomas: Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, 2006.

[11]   Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal: Computing with noisy information. SIAM J. Comput., 23(5):1001–1018, 1994. Conference version in STOC’90. [doi:10.1137/S0097539791195877]

[12]   Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, and Jérémie Roland: Relative discrepancy does not separate information and communication complexity. ACM Trans. Comput. Theory, 9(1):4:1–4:15, 2016. Conference version in ICALP’15. [doi:10.1145/2967605]

[13]   Anat Ganor, Gillat Kol, and Ran Raz: Exponential separation of information and communication. In Proc. 55th FOCS, pp. 176–185. IEEE Comp. Soc. Press, 2014. [doi:10.1109/FOCS.2014.27]

[14]   Anat Ganor, Gillat Kol, and Ran Raz: Exponential separation of communication and external information. In Proc. 48th STOC, pp. 977–986. ACM Press, 2016. [doi:10.1145/2897518.2897535]

[15]   Anat Ganor, Gillat Kol, and Ran Raz: Exponential separation of information and communication for Boolean functions. J. ACM, 63(5):46:1–46:31, 2016. Conference version in STOC’15. [doi:10.1145/2907939]

[16]   Prahladh Harsha, Rahul Jain, David A. McAllester, and Jaikumar Radhakrishnan: The communication complexity of correlation. IEEE Trans. Inform. Theory, 56(1):438–449, 2010. Conference version in CCC’07. [doi:10.1109/TIT.2009.2034824]

[17]   Bala Kalyanasundaram and Georg Schnitger: 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]

[18]   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 J. Comput., 44(5):1550–1572, 2015. Conference version in FOCS’12. [doi:10.1137/130928273, arXiv:1204.1505]

[19]   Gillat Kol: Interactive compression for product distributions. In Proc. 48th STOC, pp. 987–998. ACM Press, 2016. [doi:10.1145/2897518.2897537]

[20]   Eyal Kushilevitz and Noam Nisan: Communication Complexity. Cambridge University Press, 1997.

[21]   Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao: 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]

[22]   Sivaramakrishnan Natarajan Ramamoorthy and Makrand Sinha: 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]

[23]   Jaikumar Radhakrishnan: Entropy and counting. In Computational Mathematics, Modelling and Algorithms, pp. 146–168. Narosa Publishers, 2003. Available from author’s home page.

[24]   Anup Rao and Makrand Sinha: Simplified separation of information and communication. Electron. Colloq. on Comput. Complexity (ECCC), 2015. [ECCC:TR15-057]

[25]   Alexander A. Razborov: On the distributional complexity of disjointness. Theoret. Comput. Sci., 106(2):385–390, 1992. Conference version in ICALP’90. [doi:10.1016/0304-3975(92)90260-M]

[26]   Claude E. 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]

[27]   Alexander A. Sherstov: Compressing interactive communication under product distributions. SIAM J. Comput., 47(2):367–419, 2018. Conference version in FOCS’16. [doi:10.1137/16M109380X]

[28]   Emanuele Viola: The communication complexity of addition. Combinatorica, 35(6):703–747, 2015. Conference version in SODA’13. [doi:10.1007/s00493-014-3078-3]