## Abstract

This paper considers the problem of evaluating a function f(x,y) (x member of R_{m}, y member of R_{n}) using two processors P_{1} and P_{2}, assuming that processor P_{1} (respectively, P_{2}) has access to input x (respectively, y) and the functional form of f. A new general lower bound is established on the communication complexity (i.e., the minimum number of real-valued messages that have to be exchanged). The result is then applied to the case where f(x,y) is defined as a root z of a polynomial equation Σ_{i=0}^{n-1} (x_{i} + y_{i})z^{i} = 0 and a lower bound of n is obtained. This is in contrast to the Ω (1) lower bound obtained by applying earlier results of Abelson.

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

Pages (from-to) | 936-950 |

Number of pages | 15 |

Journal | SIAM Journal on Computing |

Volume | 20 |

Issue number | 5 |

DOIs | |

State | Published - 1991 |