# COMMUNICATION COMPLEXITY book This page contains some information related to the book Communication Complexity'', by Eyal Kushilevitz and Noam Nisan that was published by Cambridge University Press. The information here intends to be mainly a list of comments, known errors (and hopefully their corrections) etc. Some other details about the book can be found HERE. You can also visit the page of Amazon Books to order the book.
Many of the items below were reported by Bill Gasarch. We thank him very much for his careful reading of our book.

# Table of Contents

• Page (vi): Some of the page numbers listed here for the sections of Chapter 4 are larger by 1 than the actual page number.

# Chapter 1

• Page (5) Figure 1.2: The table does not completely correspond to the protocol tree in Figure 1.1. The table should instead be:
 y y' y'' y''' x 0 0 0 1 x' 0 0 0 1 x'' 0 1 1 1 x''' 0 0 0 0

• Page (6) Example 1.6: We emphasize that the term multiset'' refers to a set in which the same element may appear several times. In particular, if x and y are not disjoint their union will contain some elements more than once. The median of the union counts each element according to the number of times it appears in the multiset. This is crucial for the correctness of the protocol presented in this example.
• Examples 1.25 and 1.29: It is shown that D(IP) is at least n but it can be shown that D(IP)=n+1. This should be added to Exercise 1.30 (but can be proved by other methods as well).

# Chapter 2

• Page (22) Line (-6): In the definition of ${\vec_v}_x$, the summation should also say that z is different than x.
• Page (27) Line (2): Add the word "of" between the words "number" and "entries".

# Chapter 3

• Page (32) The second part of Open Problem 3.11 (starting with the words "How about...") should be omitted. The complement of the DISJ function provides a simple counterexample. (Thanks to Martin Sauerhoff for pointing this out.)
• Page (37) Definition 3.24 and Exercise 3.25: the complexity measures here are all zero-error measures (that is, protocol are not allowed to err but the communication complexity is measures as the expectation with respect to the distribution under consideration). So, for example, Duniform should be interpreted as D0uniform.

# Chapter 4

• Page (59) Line (-10): It is written that "BPP-coNP" is non-empty but it should say that "coNP-BPP" is non-empty.
• Page (67) Line (22): "Babal" should be "Babai".

# Chapter 5

• Page (80) Claim 5.19 4th line: "for that" should be "such that".

# Chapter 8

• Open problem 8.6 was solved by Martin Dietzfelbinger (The Linear-Array Problem in Communication Complexity Resolved'', STOC97, pp. 373--382).

# Chapter 12

• Page 145 Lemma 12.14 second line of the proof: add "disjoint" between "two" and "sets" (this is implicit by the goodness'' property of the sets but better be made explicit). Page 146 1st line: again, add "disjoint" between "two" and "sets".

# Answers to Selected Problems (pages 168-175)

• The second part of the solution to Exercise 1.7 (i.e., the one that achieves O(log n) communication complexity) needs the following clarification. If Alice holds a, Bob hold b and WLOG a is smaller than b then in future iterations it might happen that Alice's median is larger than b (or Bob's median is smaller than a). In such a case there is no reason to transmit this value. In such a case Alice can pretend as if her median in that iteration is b (or Bob pretends as if its median in that iteration is a, respectively). Alternatively, they can exchange some O(1) bits per iteration to indicate to each other whether this is the case.

# Index (pages 187-189)

• Omit 83 from the entry "generalized inner product function (GIP)".
• Add 112 to the entry "VLSI".

If you have additional comments please send them to eyalk@cs.technion.ac.il  Your visit here is number since counting re-started ....