Abstract
Summary form only given, as follows. The authors consider the problem of evaluating a function (x,y) (x ε Rm, y ε 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. The processors perform this computation by exchanging messages under the restriction that a message sent by any processor is a continuously differentiable function of the data (x or y) possessed by that processor and the messages that it has already received. 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, as well as some general properties of optimal protocols). The results are applied to the case in which f(x,y) is defined as a root z of a polynomial equation Σ(xi + yi)zi) = 0, i = 0, ..., n - 1, and a lower bound of n (which matches the obvious upper bound) is obtained. This is in contrast to the Ω(1) lower bound obtained by applying earlier results of Abelson. The results, although very intuitive, are surprisingly difficult to prove and involve primarily techniques from multivariable calculus.
Original language | English (US) |
---|---|
Title of host publication | 1990 IEEE Int Symp Inf Theor |
Publisher | Publ by IEEE |
Number of pages | 1 |
State | Published - Dec 1 1990 |
Event | 1990 IEEE International Symposium on Information Theory - San Diego, CA, USA Duration: Jan 14 1990 → Jan 19 1990 |
Other
Other | 1990 IEEE International Symposium on Information Theory |
---|---|
City | San Diego, CA, USA |
Period | 1/14/90 → 1/19/90 |