Communication complexity of algebraic computation

Zhi Quan Luo, John N. Tsitsiklis

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations


The authors consider a situation in which two processors P1 and P2 are to evaluate one or more functions f1,..., fs of two vector variables x and y, under the assumption that processor P1 (respectively, P2) has access only to the value of x (respectively, y) and the functional form of f1,...,fs. 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 fi 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 Σ(xi + yi)zi = 0, where the sum is from i = 0 to n - 1.

Original languageEnglish (US)
Pages (from-to)758-765
Number of pages8
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 1990
EventProceedings of the 31st Annual Symposium on Foundations of Computer Science - St. Louis, MO, USA
Duration: Oct 22 1990Oct 24 1990


Dive into the research topics of 'Communication complexity of algebraic computation'. Together they form a unique fingerprint.

Cite this