Communication complexity of algebraic computation

The authors consider a situation in which two processors P₁ and P₂ are to evaluate one or more functions f₁, . . ., f_s of two vector variables x and y, under the assumption that processor P₁ (respectively, P₂ ) has access only to the value of x (respectively, y ) and the functional form of f₁, . . ., f _s. They consider a continuous model of communication whereby real-valued messages are transmitted, and they study the minimum number of messages required for the desired computation. Tight lower bounds are established for the following three problems: (1) each f _i is a rational function and only one-way communication is allowed. (2) The variables x and y are matrices and the processors wish to solve the linear system (x+y) z=b for the unknown z. (3) The processors wish to evaluate a particular root of the polynomial equation Σ( x_i+y_i)zⁱ=0, where the sum is from i=0 to n-1