Communication complexity. (English) Zbl 0869.68048

Cambridge: Cambridge Univ. Press. xiii, 189 p. (1997).
In this monograph two experts in the field develop an almost complete picture of the various aspects of communication complexity and its applications. Communication complexity deals with the problem of what to communicate rather than of how to communicate (as in information and coding theory). The aim is always for several parties to solve a certain task, where the parties involved don’t have full information about the input. The question is, how many bits of communication are necessary and sufficient to jointly solve the task. This situation is met in an abstract way in many (if not all) kinds of computations and it can be concisely formulated and considered in mathematical terms. Knowledge of the complexity of a certain communication problem often allows to derive conclusions about the original computational problem. The wide applicability of the techniques as well as the mathematical beauty of the problems and their solutions make this field a fascinating and fruitful subject of research.
Part 1 covers the two-party case from the basic deterministic model over nondeterministic and randomized extensions to advanced topics (direct sum, asymmetric communication, pseudorandomness, communication with partial information). Part 2 deals with other communication games: relations, multiparty communication, variable partition. Part 3 is devoted to the many applications of communication complexity to various models of computation: networks and VLSI circuits, decision trees, Boolean circuits, and Turing machines.
The book contains many examples and exercises (partly with solutions) as well as research problems. Each chapter is equipped with a set of bibliographic notes.
Reviewer: C.Damm (Trier)


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68-02 Research exposition (monographs, survey articles) pertaining to computer science
94A05 Communication theory
Full Text: DOI