[1]   Noga Alon and Joel H. Spencer: The Probabilistic Method. John Wiley & Sons, 3rd edition, 2008. [doi:10.1002/9780470277331]

[2]   László Babai, Péter Frankl, and János 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]   Paul Beame, Toniann Pitassi, Nathan Segerlind, and Avi Wigderson: A strong direct product theorem for corruption and the multiparty communication complexity of disjointness. Comput. Complexity, 15(4):391–432, 2006. [doi:10.1007/s00037-007-0220-2]

[4]   Joshua Brody and Amit Chakrabarti: A multi-round communication lower bound for gap Hamming and some consequences. In Proc. 24th IEEE Conf. on Computational Complexity (CCC’09), pp. 358–368. IEEE Comp. Soc. Press, 2009. [doi:10.1109/CCC.2009.31]

[5]   Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, and Ronald de Wolf: Better gap-Hamming lower bounds via better round elimination. In Proc. 15th Internat. Workshop on Randomization and Computation (RANDOM’10), pp. 476–489. Springer, 2010. [doi:10.1007/978-3-642-15369-3_36]

[6]   Amit Chakrabarti, Graham Cormode, and Andrew McGregor: A near-optimal algorithm for estimating the entropy of a stream. ACM Trans. Algorithms, 6(3), 2010. [doi:10.1145/1798596.1798604]

[7]   Amit Chakrabarti and Oded Regev: An optimal lower bound on the communication complexity of gap-Hamming-distance. In Proc. 43rd STOC, pp. 51–60. ACM Press, 2011. [doi:10.1145/1993636.1993644]

[8]   Piotr Indyk and David P. Woodruff: Tight lower bounds for the distinct elements problem. In Proc. 44th FOCS, pp. 283–289. IEEE Comp. Soc. Press, 2003. [doi:10.1109/SFCS.2003.1238202]

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

[10]   T. S. Jayram, Ravi Kumar, and D. Sivakumar: The one-way communication complexity of Hamming distance. Theory of Computing, 4(1):129–135, 2008. [doi:10.4086/toc.2008.v004a006]

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

[12]   Eyal Kushilevitz and Noam Nisan: Communication complexity. Cambridge University Press, 1997. [doi:10.1017/CBO9780511574948]

[13]   Ran Raz: Exponential separation of quantum and classical communication complexity. In Proc. 31st STOC, pp. 358–367. ACM Press, 1999. [doi:10.1145/301250.301343]

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

[15]   Michel Talagrand: Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de L’IHÉS, 81(1):73–205, 1996. [doi:10.1007/BF02699376]

[16]   Terence Tao: Talagrand’s concentration inequality. Weblog entry, 2009. http://terrytao.wordpress.com/2009/06/09/talagrands-concentration-inequality/.

[17]   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. Technical Report TR11-051, Electron. Colloq. on Comput. Complexity (ECCC), 2010. Revised, 2011. [ECCC:TR11-051]

[18]   David P. Woodruff: Optimal space lower bounds for all frequency moments. In Proc. 15th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’04), pp. 167–175, 2004. [ACM:982817]

[19]   David P. Woodruff: The average-case complexity of counting distinct elements. In Proceedings of the Twelfth International Conference on Database Theory (ICDT), pp. 284–295, 2009. [doi:10.1145/1514894.1514928]

[20]   Andrew Chi-Chih Yao: Lower bounds by probabilistic arguments. In Proc. 24th FOCS, pp. 420–428. IEEE Comp. Soc. Press, 1983. [doi:10.1109/SFCS.1983.30]