Communication Complexity Theory: Models, Techniques, Applications

Dr. Satyanarayana V. Lokam
Department of Computer Science
University of Chicago

Monday, February 26, 1996
11 a.m. - 12 noon
Salisbury Labs 104

In the theory of computing, we are interested in the inherent complexity of computation. The famous "P vs NP" question is an example. Progress on "P vs NP" has been slow due to our lack of proper understanding of the Turing-machine model. On the other hand, a number of combinatorial and algebraic models of computation have been developed in the past two decades and used with considerable success for gaining insight into the complexity of computation. Such models include Boolean and algebraic circuits, decision trees, and branching programs.

The notion of "Communication Complexity" has emerged as a central concept in these areas. In this abstract model, two processors each receive half of the input to a computational task. The objective is to minimize the amount of communication required between the processors for the computation. Originally invented to study the complexity of VLSI computations, communication complexity has been applied in a variety of contexts.

Extending a result of Nisan and Wigderson, we give lower bounds on the complexity of computing linear transformations via arithmetic circuits. We use perturbation inequalities for singular values of a matrix to prove the underlying result in communication complexity theory.

We also study multi-party communication complexity and demonstrate a surprising way to save on communication.

Maintained by webmaster@wpi.edu
Last modified: Sep 27, 2006, 16:05 EDT