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.