{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:20:39Z","timestamp":1771485639194,"version":"3.50.1"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,6,4]],"date-time":"2015-06-04T00:00:00Z","timestamp":1433376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2015,6,4]]},"abstract":"<jats:p>Information complexity is the interactive analogue of Shannon's classical information theory. In recent years this field has emerged as a powerful tool for proving strong communication lower bounds, and for addressing some of the major open problems in communication complexity and circuit complexity. A notable achievement of information complexity is the breakthrough in understanding of the fundamental direct sum and direct product conjectures, which aim to quantify the power of parallel computation. This survey provides a brief introduction to information complexity, and overviews some of the recent progress on these conjectures and their tight relationship with the fascinating problem of compressing interactive protocols.<\/jats:p>","DOI":"10.1145\/2789149.2789161","type":"journal-article","created":{"date-parts":[[2015,6,8]],"date-time":"2015-06-08T15:11:11Z","timestamp":1433776271000},"page":"41-64","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Information Complexity and the Quest for Interactive Compression"],"prefix":"10.1145","volume":"46","author":[{"given":"O.","family":"Weinstein","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ"}]}],"member":"320","published-online":{"date-parts":[[2015,6,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806701"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.12"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0040-x"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Mark Braverman Faith Ellen Rotem Oshman Toniann Pitassi and Vinod Vaikuntanathan. Tight bounds for set disjointness in the message passing model. CoRR abs\/1305.4696 2013. Mark Braverman Faith Ellen Rotem Oshman Toniann Pitassi and Vinod Vaikuntanathan. Tight bounds for set disjointness in the message passing model. CoRR abs\/1305.4696 2013.","DOI":"10.1109\/FOCS.2013.77"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488628"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Mark Braverman and Ankur Moitra. An information complexity approach to extended formulations. Electronic Colloquium on Computational Complexity (ECCC) 19:131 2012. Mark Braverman and Ankur Moitra. An information complexity approach to extended formulations. Electronic Colloquium on Computational Complexity (ECCC) 19:131 2012.","DOI":"10.1145\/2488608.2488629"},{"key":"e_1_2_1_7_1","unstructured":"Balthazar Bauer Shay Moran and Amir Yehudayo_. Internal compression of protocols to entropy. Electronic Colloquium on Computational Complexity (ECCC) 21:101 2014. Balthazar Bauer Shay Moran and Amir Yehudayo_. Internal compression of protocols to entropy. Electronic Colloquium on Computational Complexity (ECCC) 21:101 2014."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.79"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.86"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214025"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/Allerton.2013.6736498"},{"key":"e_1_2_1_12_1","unstructured":"Mark Braverman. Interactive information and coding theory. 2014. Mark Braverman. Interactive information and coding theory. 2014."},{"key":"e_1_2_1_13_1","unstructured":"Mark Braverman Anup Rao Omri Weinstein and Amir Yehudayo_. Direct products in communication complexity. Electronic Colloquium on Computational Complexity (ECCC) 19:143 2012. Mark Braverman Anup Rao Omri Weinstein and Amir Yehudayo_. Direct products in communication complexity. Electronic Colloquium on Computational Complexity (ECCC) 19:143 2012."},{"key":"e_1_2_1_14_1","unstructured":"Mark Braverman Anup Rao Omri Weinstein and Amir Yehudayo_. Direct product via round-preserving compression. Electronic Colloquium on Computational Complexity (ECCC) 20:35 2013. Mark Braverman Anup Rao Omri Weinstein and Amir Yehudayo_. Direct product via round-preserving compression. Electronic Colloquium on Computational Complexity (ECCC) 20:35 2013."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185449"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_39"},{"key":"e_1_2_1_17_1","unstructured":"Mark Braverman and Omri Weinstein. An interactive information odometer with applications. Electronic Colloquium on Computational Complexity (ECCC) 21:47 2014. Mark Braverman and Omri Weinstein. An interactive information odometer with applications. Electronic Colloquium on Computational Complexity (ECCC) 21:47 2014."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214414"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875561"},{"key":"e_1_2_1_21_1","unstructured":"Thomas M. Cover and Joy A. Thomas . Elements of Information Theory . Wiley series in telecommunications . J. Wiley and Sons New York 1991 . Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley series in telecommunications. J. Wiley and Sons New York 1991."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-011-2528-4"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792235864"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791195877"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Anat Ganor Gillat Kol and Ran Raz. Exponential separation of information and communication. Electronic Colloquium on Computational Complexity (ECCC) 21:49 2014. Anat Ganor Gillat Kol and Ran Raz. Exponential separation of information and communication. Electronic Colloquium on Computational Complexity (ECCC) 21:49 2014.","DOI":"10.1109\/FOCS.2014.27"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591856"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.37"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.32"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250852"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"e_1_2_1_32_1","unstructured":"Rahul Jain. New strong direct product results in communication complexity. 2011. Rahul Jain. New strong direct product results in communication complexity. 2011."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.39"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.42"},{"key":"e_1_2_1_35_1","unstructured":"Rahul Jain and Penghui Yao. A strong direct product theorem in terms of the smooth rectangle bound. CoRR abs\/1209.0263 2012. Rahul Jain and Penghui Yao. A strong direct product theorem in terms of the smooth rectangle bound. CoRR abs\/1209.0263 2012."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806702"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.68"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206317"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62265"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-010-0292-2"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.25"},{"key":"e_1_2_1_42_1","volume-title":"SODA, page to appear","author":"Molinaro Marco","year":"2013"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258620"},{"key":"e_1_2_1_44_1","first-page":"1065","volume-title":"SODA","author":"Patrascu Mihai","year":"2010"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374378"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_1_48_1","first-page":"27","article-title":"A mathematical theory of communication","author":"Shannon Claude E.","year":"1948","journal-title":"Bell System Technical Journal"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-003-0175-x"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/110842661"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Mert Saglam and G_abor Tardos. On the communication complexity of sparse set disjointness and exists-equal problems. CoRR abs\/1304.1217 2013. Mert Saglam and G_abor Tardos. On the communication complexity of sparse set disjointness and exists-equal problems. CoRR abs\/1304.1217 2013.","DOI":"10.1109\/FOCS.2013.78"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Juraj Waczulk . Area time squared and area complexity of vlsi computations is strongly unclosed under union and intersection. In Jrgen Dassow and Jozef Kelemen editors Aspects and Prospects of Theoretical Computer Science volume 464 of Lecture Notes in Computer Science pages 278 -- 287 . Springer Berlin Heidelberg 1990 . Juraj Waczulk. Area time squared and area complexity of vlsi computations is strongly unclosed under union and intersection. In Jrgen Dassow and Jozef Kelemen editors Aspects and Prospects of Theoretical Computer Science volume 464 of Lecture Notes in Computer Science pages 278--287. Springer Berlin Heidelberg 1990.","DOI":"10.1007\/3-540-53414-8_51"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_2_1_54_1","first-page":"718","volume-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014","author":"Qin Zhang David P.","year":"2014"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"},{"key":"e_1_2_1_56_1","first-page":"80","volume-title":"FOCS","author":"Chi-Chih Yao Andrew","year":"1982"},{"key":"e_1_2_1_57_1","volume-title":"Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held","author":"Zhang Yuchen","year":"2013"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2789149.2789161","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2789149.2789161","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:42:50Z","timestamp":1750225370000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2789149.2789161"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,4]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6,4]]}},"alternative-id":["10.1145\/2789149.2789161"],"URL":"https:\/\/doi.org\/10.1145\/2789149.2789161","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2015,6,4]]},"assertion":[{"value":"2015-06-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}