## Abstract

The authors consider a situation in which two processors P_{1} and P_{2} are to evaluate one or more functions f_{1},..., f_{s} of two vector variables x and y, under the assumption that processor P_{1} (respectively, P_{2}) has access only to the value of x (respectively, y) and the functional form of f_{1},...,f_{s}. 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 f_{i} 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 Σ(x_{i} + y_{i})z^{i} = 0, where the sum is from i = 0 to n - 1.

Original language | English (US) |
---|---|

Pages (from-to) | 758-765 |

Number of pages | 8 |

Journal | Annual Symposium on Foundations of Computer Science - Proceedings |

Volume | 2 |

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 |