On the communication complexity of solving a polynomial equation

Zhi Quan Luo, John N. Tsitsiklis

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

This paper considers the problem of evaluating a function f(x,y) (x member of Rm, y member of 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. 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=0n-1 (xi + yi)zi = 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.

Original languageEnglish (US)
Pages (from-to)936-950
Number of pages15
JournalSIAM Journal on Computing
Volume20
Issue number5
DOIs
StatePublished - Jan 1 1991

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

  • Cite this