Communication complexity and parallel computing

Publication date 21 May 1997

Boolean circuits branching programs communication complexity communication protocol models complexity measures decision trees interconnection networks multilective VLSI circuits

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02)

Review text

Communication complexity is considered to be one of the fundamental complexity measures in recent complexity theory. It is used as a method for investigating the complexity of concrete computational problems. In particular, communication complexity provides rather powerful means for proving lower bounds on the amount of computational resources for concrete problems. The investigation of the communication complexity has contributed to the understanding of the nature of determinism, nondeterminism, and randomness in algorithmics. The book under consideration presents the basic concepts and ideas, and introduces into todays most important applications of communication complexity consideration. The first chapter, Introduction, describes motivations and aims of the book, and explains its concept and organization. Chapter 2, Communication Protocol Models, deals with communication complexity as an abstract complexity measure. It is divided into seven sections. The first section, Basic Notions (2.1), provides definitions and basic notions from formal languages, Boolean functions, and graph theory. Communication Complexity According to a Fixed Partition (2.2), introduces the computational model of two-parity protocols and starts with the investigation of the communication complexity according to fixed partitions of the input. In Communication Complexity (2.3) the general communication complexity measure is defined and investigated. In One-Way Communication Complexity (2.4) the basic lower bounds for one-way communication complexity are presented and compared to simultaneous results for the communication complexity. Nondeterministic Communication Complexity and Randomized Protocols (2.5) compares the computational power of the different computational models with respect to the corresponding communication complexity measures. In An Improved Model of Communication Protocols (2.6) the author proposes a new model for the investigation of the communication complexity that can be applied e.g. to prove lower bounds on parallel computations even in cases the standard model fails to do so. Chapter 3, Boolean Circuits is devoted to the relation between communication complexity and various complexity measures for Boolean circuits. As all the following chapters it starts with an introduction. In Definitions and Fundamental Properties (3.2), Boolean circuits and the relevant complexity measures are introduced. Lower Bounds on the Area of Boolean Circuits (3.3) shows how the communication complexity provides lower bounds on the layout area of any Boolean circuit. Topology of Circuits and Lower Bounds (3.4) deals with the classical open problem of proving a nonlinear lower bound on the combinational circuit complexity. In Lower Bounds on the Size of Unbounded Fan-in Circuits (3.5) communication complexity is related to the investigation of the size of Boolean circuits with unbounded fan-in while Lower Bounds on the Depth of Boolean Circuits (3.6) considers this relation with respect to depth. Chapter 4, VLSI Circuits and Interconnection Networks, deals with the consideration of connections between communication complexity and various VLSI circuit models. In Definitions (4.2) these VLSI circuit models are introduced. Lower Bounds on VLSI Complexity Measures (4.3) shows that one-way communication complexity can be used to obtain lower bounds on the tradeoffs between area and time complexity of VLSI circuits. Interconnection Networks (4.4) describes a rather powerful model of interconnection networks and shows how to apply communication complexity to obtain lower bounds for this model. In Multilective VLSI circuits (4.5) a generalized model of VLSI circuits is considered. The final Chapter 5, Sequential Computations, is devoted to the description of relations between communication complexity and other relevant complexity measures for sequential computations. In Finite Automata (5.2), it is shown that uniform one-way communication complexity is strongly related to the size of deterministic finite automata. Turing Machines (5.3) relates communication complexity to the size and space complexity of Turing machines. In Decision Trees and Branching Programs (5.4) corresponding relations are considered for the both models of branching programs and decision diagrams. Almost each section of the five chapters concludes with the subsections Exercises and Research. Each chapter is rounded off with a section containing detailed and informative bibliographic notes. By the way, it seems to me that all -- at least all relevant -- research papers in the field are mentioned in the 14 pages of references. Altogether, students and researchers interested in the field of complexity theory, get an informative compendium at their disposal. Formulations are precise, and the proofs are exact and complete. The relatively high degree of formalization seems to be necessary for being able to completely present all the clever lower bound arguments. The text is suited for the beginner as introduction into the field as well as for researcher as a very detailed compendium and reference. In any case, the book should be contained in the library of each complexity theorist.

Recommendations

Cited in

(74)

This page was built for publication: Communication complexity and parallel computing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4337605)