## Abstract

Consideration is given to a situation in which two processors, P_{1} and P_{2}, are to evaluate a collection of functions f_{1},..., f]_{s} of two vector variables x, y under the assumption that processor P_{1} (respectively, P_{2}) has access only to the value of the variable x (respectively, y) and the functional form of f_{1}, ..., f_{s}. Bounds on the communication complexity (the amount of information that has to be exchanged between the processors) are provided. An almost optimal bound is derived for the case of one-way communication when the functions are polynomials. Lower bounds for the case of two-way communication that improve on earlier bounds are also derived. As an application, the case in which x and y are n × n matrices and f(x,y) is a particular entry of the inverse of x + y is considered. Under a certain restriction on the class of allowed communication protocols, an Ω(n^{2}) lower bound is obtained. The results are based on certain tools from classical algebraic geometry and field extension theory.

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

Pages (from-to) | 899-900 |

Number of pages | 2 |

Journal | Proceedings of the IEEE Conference on Decision and Control |

Volume | 1 |

State | Published - Dec 1 1989 |

Event | Proceedings of the 28th IEEE Conference on Decision and Control. Part 1 (of 3) - Tampa, FL, USA Duration: Dec 13 1989 → Dec 15 1989 |