The communication complexity of solving a polynomial equation

Zhi Quan Luo, John N. Tsitsiklis

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 languageEnglish (US)
Title of host publication1990 IEEE Int Symp Inf Theor
PublisherPubl by IEEE
Number of pages1
StatePublished - Dec 1 1990
Event1990 IEEE International Symposium on Information Theory - San Diego, CA, USA
Duration: Jan 14 1990Jan 19 1990


Other1990 IEEE International Symposium on Information Theory
CitySan Diego, CA, USA


Dive into the research topics of 'The communication complexity of solving a polynomial equation'. Together they form a unique fingerprint.

Cite this