[1]   Scott Aaronson and Avi Wigderson: Algebrization: A new barrier in complexity theory. ACM Trans. Comput. Theory, 1(1):2:1–2:54, 2009. Prelimianry version in STOC’08. [doi:10.1145/1490270.1490272]

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

[3]   László Babai and Shlomo Moran: Arthur–Merlin games: A randomized proof system, and a hierarchy of complexity classes. J. Comput. System Sci., 36(2):254–276, 1988. [doi:10.1016/0022-0000(88)90028-1]

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

[5]   Elmar Böhler, Christian Glaßer, and Daniel Meister: Error-bounded probabilistic computations between MA and AM. J. Comput. System Sci., 72(6):1043–1076, 2006. Preliminary version in MFCS’03. [doi:10.1016/j.jcss.2006.05.001]

[6]   Gábor Braun, Samuel Fiorini, Sebastian Pokutta, and David Steurer: Approximation limits of linear programs (beyond hierarchies). Math. Oper. Res., 40(3):756–772, 2015. Preliminary version in FOCS’12. [doi:10.1287/moor.2014.0694, arXiv:1204.0957]

[7]   Gábor Braun and Sebastian Pokutta: Common information and unique disjointness. Algorithmica, pp. 1–33, 2016. Preliminary versions in FOCS’13 and ECCC. [doi:10.1007/s00453-016-0132-0]

[8]   Mark Braverman and Ankur Moitra: An information complexity approach to extended formulations. In Proc. 45th STOC, pp. 161–170. ACM Press, 2013. Preliminary version in ECCC. [doi:10.1145/2488608.2488629]

[9]   Mark Braverman and Omri Weinstein: A discrepancy lower bound for information complexity. In Proc. 16th Internat. Workshop on Randomization and Computation (RANDOM’12), pp. 459–470. Springer, 2012. Preliminary version in ECCC. [doi:10.1007/978-3-642-32512-0_39, arXiv:1112.2000]

[10]   Harry Buhrman, Nikolai Vereshchagin, and Ronald de Wolf: On computation and communication with small bias. In Proc. 22nd IEEE Conf. on Computational Complexity (CCC’07), pp. 24–32. IEEE Comp. Soc. Press, 2007. [doi:10.1109/CCC.2007.18]

[11]   Amit Chakrabarti, Graham Cormode, Andrew McGregor, and Justin Thaler: Annotations in data streams. ACM Trans. Algorithms, 11(1):7, 2014. Preliminary version in ECCC. [doi:10.1145/2636924]

[12]   Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian: Verifiable stream computation and Arthur–Merlin communication. In Proc. 30th IEEE Conf. on Computational Complexity (CCC’15), pp. 217–243. Schloss Dagstuhl, 2015. Preliminary version in ECCC. [doi:10.4230/LIPIcs.CCC.2015.217]

[13]   Amit Chakrabarti and Oded Regev: An optimal lower bound on the communication complexity of Gap-Hamming-Distance. SIAM J. Comput., 41(5):1299–1317, 2012. Preliminary version in STOC’11. [doi:10.1137/120861072, arXiv:1009.3460]

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

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

[16]   Thomas Cover and Joy Thomas: Elements of Information Theory. Wiley, 2006.

[17]    Scott Diehl: Lower bounds for swapping Arthur and Merlin. In Proc. 11th Internat. Workshop on Randomization and Computation (RANDOM’07), pp. 449–463. Springer, 2007. [doi:10.1007/978-3-540-74208-1_33]

[18]    Jürgen Forster: A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. System Sci., 65(4):612–625, 2002. Preliminary version in CCC’01. [doi:10.1016/S0022-0000(02)00019-3]

[19]   Anat Ganor, Gillat Kol, and Ran Raz: Exponential separation of information and communication for boolean functions. In Proc. 47th STOC, pp. 557–566. ACM Press, 2015. Preliminary version in ECCC. [doi:10.1145/2746539.2746572]

[20]   Shafi Goldwasser and Michael Sipser: Private coins versus public coins in interactive proof systems. In Proc. 18th STOC, pp. 59–68. ACM Press, 1986. [doi:10.1145/12130.12137]

[21]   Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman: Rectangles are nonnegative juntas. In Proc. 47th STOC, pp. 257–266. ACM Press, 2015. Preliminary version in ECCC. [doi:10.1145/2746539.2746596]

[22]   Mika Göös and Thomas Watson: Communication complexity of set-disjointness for all probabilities. In Proc. 18th Internat. Workshop on Randomization and Computation (RANDOM’14), pp. 721–736. Schloss Dagstuhl, 2014. Preliminary versin in ECCC. [doi:10.4230/LIPIcs.APPROX-RANDOM.2014.721]

[23]   Tom Gur and Ran Raz: Arthur–Merlin streaming complexity. Inform. and Comput., 243:145–165, 2015. Preliminary version in ICALP’13. [doi:10.1016/j.ic.2014.12.011, arXiv:1302.0418]

[24]   Rahul Jain and Hartmut Klauck: The partition bound for classical communication complexity and query complexity. In Proc. 25th IEEE Conf. on Computational Complexity (CCC’10), pp. 247–258. IEEE Comp. Soc. Press, 2010. [doi:10.1109/CCC.2010.31, arXiv:0910.4266]

[25]   Rahul Jain, Troy Lee, and Nisheeth Vishnoi: A quadratically tight partition bound for classical communication complexity and query complexity, 2014. [arXiv:1401.4512]

[26]   Stasys Jukna: Boolean Function Complexity: Advances and Frontiers. Volume 27 of Algorithms and Combinatorics. Springer, 2012. [doi:10.1007/978-3-642-24508-4]

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

[28]   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. Preliminary versions in FOCS’12 and ECCC. [doi:10.1137/130928273, arXiv:1204.1505]

[29]   Hartmut Klauck: Rectangle size bounds and threshold covers in communication complexity. In Proc. 18th IEEE Conf. on Computational Complexity (CCC’03), pp. 118–134. IEEE Comp. Soc. Press, 2003. [doi:10.1109/CCC.2003.1214415, arXiv:cs/0208006]

[30]   Hartmut Klauck: Lower bounds for quantum communication complexity. SIAM J. Comput., 37(1):20–46, 2007. Preliminary version in FOCS’01. [doi:10.1137/S0097539702405620, arXiv:quant-ph/0106160]

[31]   Hartmut Klauck: On Arthur Merlin games in communication complexity. In Proc. 26th IEEE Conf. on Computational Complexity (CCC’11), pp. 189–199. IEEE Comp. Soc. Press, 2011. [doi:10.1109/CCC.2011.33, arXiv:1101.0523]

[32]   Eyal Kushilevitz and Noam Nisan: Communication Complexity. Cambridge Univ. Press, 1997.

[33]   Ilan Newman: Private vs. common random bits in communication complexity. Inform. Process. Lett., 39(2):67–71, 1991. [doi:10.1016/0020-0190(91)90157-D]

[34]   Ramamohan Paturi and Janos Simon: Probabilistic communication complexity. J. Comput. System Sci., 33(1):106–123, 1986. Preliminary version in FOCS’84. [doi:10.1016/0022-0000(86)90046-2]

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

[36]   Alexander A. Sherstov: Halfspace matrices. Comput. Complexity, 17(2):149–178, 2008. Preliminary version in CCC’07. [doi:10.1007/s00037-008-0242-4]

[37]   Alexander A. Sherstov: The pattern matrix method. SIAM J. Comput., 40(6):1969–2000, 2011. Preliminary version in STOC’08. [doi:10.1137/080733644, arXiv:0906.4291]

[38]    Alexander A. Sherstov: The unbounded-error communication complexity of symmetric functions. Combinatorica, 31(5):583–614, 2011. Preliminary version in FOCS’08. [doi:10.1007/s00493-011-2580-0]

[39]   Alexander A. Sherstov: The communication complexity of Gap Hamming Distance. Theory of Computing, 8(8):197–208, 2012. Preliminary version in ECCC. [doi:10.4086/toc.2012.v008a008]

[40]   Thomas Vidick: A concentration inequality for the overlap of a vector on a large set, with application to the communication complexity of the Gap-Hamming-Distance problem. Chicago J. Theoret. Comput. Sci., 2012(1):1–12, 2012. [doi:10.4086/cjtcs.2012.001]

[41]   Thomas Watson: The complexity of estimating min-entropy. Comput. Complexity, 25(1):153–175, 2016. Preliminary version in ECCC. [doi:10.1007/s00037-014-0091-2]