COMMUNICATION COMPLEXITY OF VARIOUS VLSI MODELS

Information transfer is a basic measure of complexity in distributed computation. In VLSI, communication constraints alone dictate bounds on the performance of the chips. In this thesis, we study the complexity of distributed computation under several models, using information transfer as a complexity measure. Besides deterministic protocols, we consider nondeterministic and several probabilistic protocols. We derive optimal characterizations for nondeterministic and probabilistic protocols. For the polynomial time complexity classes, the fundamental problem of proving strict containment among deterministic, nondeterministic and probabilistic computations is wide open. We settle the analogues question for the Communication Complexity classes: We prove strict containment with exponential gaps between deterministic, nondeterministic, random, bounded and unbounded error probabilistic communication complexity classes.;We develop two general lower bound techniques to estimate the communication requirements for the distributed computation of a set of boolean functions. A partial list of problems for which we have shown maximal information transfer regardless of the partitioning of the input data includes integer multiplication, integer division, matrix squaring, matrix inversion, matrix multiplication, Discrete Fourier Transform, solving a linear system of equations, computing square roots,... . The novelty in our approach is that the techniques are simple and can be easily applied to obtain optimal bounds for many problems. Moreover, using one of our lower bound techniques and Shannon's first theorem we show bounds on the average information transfer under uniform distribution of the input data. Using these results we derive bounds on area time tradeoffs and the chip area required to solve these problems under a variety of VLSI models. Finally, we translate our bounds on information transfer to area time tradeoffs for probabilistic VLSI chips.;We explore connections between 1-way and 2-way communications and strengthen the known gap for deterministic protocols. Using this and our lower bound characterizations we show exponential gaps between 1-way and 2-way probabilistic communication complexity classes. We also derive bounds on the average information transfer using relationships from Classical Information theory. Using the Von Neumann Minimax theorem these bounds are translated to bounds on Las Vegas computations.