The authors consider a situation in which two processors P1 and P2 are to evaluate one or more functions f1,..., fs of two vector variables x and y, under the assumption that processor P1 (respectively, P2) has access only to the value of x (respectively, y) and the functional form of f1,...,fs. They consider a continuous model of communication whereby real-valued messages are transmitted, and they study the minimum number of messages required for the desired computation. Tight lower bounds are established for the following three problems: (1) Each fi is a rational function and only one-way communication is allowed. (2) The variables x and y are matrices and the processors wish to solve the linear system (x + y)z = b for the unknown z. (3) The processors wish to evaluate a particular root of the polynomial equation Σ(xi + yi)zi = 0, where the sum is from i = 0 to n - 1.
|Original language||English (US)|
|Number of pages||8|
|Journal||Annual Symposium on Foundations of Computer Science - Proceedings|
|State||Published - 1990|
|Event||Proceedings of the 31st Annual Symposium on Foundations of Computer Science - St. Louis, MO, USA|
Duration: Oct 22 1990 → Oct 24 1990