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 ....