In this article we survey the theory of two-party communication complexity. This field of
theoretical computer science aims at studying the following, seemingly very simple …

Boolean circuit complexity is the combinatorics of computer science and involves many
intriguing problems that are easy to state and explain, even for the layman. This book is a …

This paper presents lower bound results on Boolean function complexity under two di erent
models. The rst is an abstraction of tradeo s between chip area and speed in very large …

We take a complexity theoretic view of AC Yao's theory of communication complexity. A rich
structure of natural complexity classes is introduced. Besides providing a more structured …

Parallel Sorting Algorithms explains how to use parallel algorithms to sort a sequence of
items on a variety of parallel computers. The book reviews the sorting problem, the parallel …

In this paper, we prove tight upper and lower bounds on the number or processors,
information transfer, wire area and time needed to sort N numbers in a bounded-degree …

This paper surveys nine designs for VLSI circuits that compute N-element Fourier
transforms. The largest of the designs requires O (N2 log N) units of silicon area; it can start …

In this paper, we use crossing number and wire area arguments to find lower bounds on the
layout area and maximum edge length of a variety of new and computationally useful …

The problem of error-free transmission capacity of a noisy channel was posed by Shannon
in 1956 and remains unsolved, Nevertheless, partial results for this and similar channel and …

In this paper we prove several results concerning this complexity measure. First we establish
(in a non-constructive manner) that there exist languages which cannot be recognized with …