On the communication complexity of solving a polynomial equation

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₁ and P₂, assuming that processor P₁ (respectively, P₂) 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ⁱ = 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.