Abstract
This paper considers the problem of evaluating a function f(x,y) (x member of Rm, y member of Rn) using two processors P1 and P2, assuming that processor P1 (respectively, P2) 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=0n-1 (xi + yi)zi = 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 |