Trading Information Complexity for Error

by Yuval Dagan, Yuval Filmus, Hamed Hatami, and Yaqiao Li

Theory of Computing, Volume 14(6), pp. 1-73, 2018

Bibliography with links to cited articles

[1]   László Babai, Peter Frankl, and Janos Simon: Complexity classes in communication complexity theory. In Proc. 27th FOCS, pp. 337–347. IEEE Comp. Soc. Press, 1986. [doi:10.1109/SFCS.1986.15]

[2]   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. Preliminary version in FOCS’02. [doi:10.1016/j.jcss.2003.11.006]

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

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

[5]   Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein: From information to exact communication (extended abstract). In Proc. 45th STOC, pp. 151–160. ACM Press, 2013. [doi:10.1145/2488608.2488628]

[6]   Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein: Information lower bounds via self-reducibility. Theory Comput. Syst., 59(2):377–396, 2016. Preliminary version in CSR’13. [doi:10.1007/s00224-015-9655-z]

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

[8]   Mark Braverman, Anup Rao, Omri Weinstein, and Amir Yehudayoff: Direct product via round-preserving compression. In Proc. 40th Internat. Colloq. on Automata, Languages and Programming (ICALP’13), pp. 232–243. Springer, 2013. [doi:10.1007/978-3-642-39206-1_20]

[9]   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]

[10]   Mark Braverman and Jon Schneider: Information complexity is computable. In Proc. 43rd Internat. Colloq. on Automata, Languages and Programming (ICALP’16). DROPS, 2016. [doi:10.4230/LIPIcs.ICALP.2016.87, arXiv:1502.02971]

[11]   Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew 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]

[12]   Arkadev Chattopadhyay and Toniann Pitassi: The story of set disjointness. SIGACT News, 41(3):59–85, 2010. [doi:10.1145/1855118.1855133]

[13]   Yuval Dagan, Yuval Filmus, Hamed Hatami, and Yaqiao Li: Trading information complexity for error. In Proc. 32nd IEEE Conf. on Computational Complexity (CCC’17), pp. 16:1–16:59. DROPS, 2017. [doi:10.4230/LIPIcs.CCC.2017.16, arXiv:1611.06650]

[14]   Tomás Feder, Eyal Kushilevitz, Moni Naor, and Noam Nisan: Amortized communication complexity. SIAM J. Comput., 24(4):736–750, 1995. Preliminary version in CCC’17. [doi:10.1137/S0097539792235864]

[15]   Yuval Filmus, Hamed Hatami, Yaqiao Li, and Suzin You: Information complexity of the AND function in the two-party, and multiparty settings. In Proc. 23rd Ann. Internat. Computing and Combinatorics Conf. (COCOON’17), pp. 200–211. Springer, 2017. [doi:10.1007/978-3-319-62389-4_17, arXiv:1703.07833]

[16]   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. Preliminary version in STOC’15. [doi:10.1145/2907939]

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

[18]   Rahul Jain: New strong direct product results in communication complexity. J. ACM, 62(3):20:1–20:27, 2015. Preliminary version in ECCC’11. [doi:10.1145/2699432]

[19]   Rahul Jain, Attila Pereszlényi, and Penghui Yao: A direct product theorem for bounded-round public-coin randomized communication complexity. Algorithmica, 76(3):720–748, 2016. Preliminary version in FOCS’12. [doi:10.1007/s00453-015-0100-0, arXiv:1201.1666]

[20]   Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen: A direct sum theorem in communication complexity via message compression. In Proc. 30th Internat. Colloq. on Automata, Languages and Programming (ICALP’03), pp. 300–315. Springer, 2003. [doi:10.1007/3-540-45061-0_26, arXiv:cs/0304020]

[21]   Bala Kalyanasundaram and Georg Schnitger: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math., 5(4):545–557, 1992. Preliminary version in SCT’87. [doi:10.1137/0405044]

[22]   Hartmut Klauck: A strong direct product theorem for disjointness. In Proc. 42nd STOC, pp. 77–86. ACM Press, 2010. [doi:10.1145/1806689.1806702, arXiv:0908.2940]

[23]   Eyal Kushilevitz and Noam Nisan: Communication complexity. Cambridge University Press, 1997.

[24]   Nan Ma and Prakash Ishwar: Some results on distributed source coding for interactive function computation. IEEE Trans. Inform. Theory, 57(9):6180–6195, 2011. [doi:10.1109/TIT.2011.2161916]

[25]   Nan Ma and Prakash Ishwar: The infinite-message limit of two-terminal interactive source coding. IEEE Trans. Inform. Theory, 59(7):4071–4094, 2013. Preliminary version in Allerton’09. [doi:10.1109/TIT.2013.2251412, arXiv:0908.3512]

[26]   Marco Molinaro, David P. Woodruff, and Grigory Yaroslavtsev: Beating the direct sum theorem in communication complexity with implications for sketching. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’13), pp. 1738–1756. ACM Press, 2013. [doi:10.1137/1.9781611973105.125]

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

[28]   Byron Schmuland: On the compacity of the space of probability measures. Mathematics Stack Exchange, January 18, 2014.

[29]   Claude E. Shannon: A mathematical theory of communication. Bell System Technical Journal, 27(3):379–423, 1948. [doi:10.1002/j.1538-7305.1948.tb01338.x]

[30]   Alexander A. Sherstov: Communication complexity theory: Thirty-five years of set disjointness. In Proc. 39th Internat. Symp. on Mathematical Foundations of Computer Science (MFCS’14), pp. 24–43. Springer, 2014. [doi:10.1007/978-3-662-44522-8_3]

[31]   Andrew Chi-Chih Yao: Some complexity questions related to distributive computing (Preliminary report). In Proc. 11th STOC, pp. 209–213. ACM Press, 1979. [doi:10.1145/800135.804414]