On the Communication Complexity of Solving a Polynomial Equation
Abstract
In a computer network where a set of processors wish to perform some computational task, communication can sometimes become a bottleneck, especially when communication resources are scarce. This is particularly so, in the area of parallel and VLSI computation where communication issues have been studied extensively. In such contexts, it is desirable to design algorithms that require as little information exchange as possible. Problems of minimizing the amount of exchanged information also arise in the context of decentralized signal processing, where each local processor collects some partial data to be processed collectively. In this paper, we study the communication complexity (i. e., the minimum possible amount of information exchange) of some particular computational tasks. Generally speaking, communication complexity depends both on the topology of a computer network and on the nature of the computational task under consideration. In this paper, we ignore the topological issues, by assuming that there are only two processors, say P1 and P2.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1989
- Accession Number
- ADA211945
Entities
People
- John N. Tsitsiklis
- Zhi-quan Luo
Organizations
- Massachusetts Institute of Technology