One-way communication complexity of computing a collection of rational functions

Zhi Quan Luo

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of evaluating a collection of rational functions f(hook)1(x, y), f(hook)2(x, y), ⋯, f(hook)s(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(hook). We establish, by way of algebraic field extension theory, an almost optimal lower bound on the one-way communication complexity (i.e. the minimum number of real-valued messages that have to be exchanged). Our result strengthens the early result of Abelson in several directions.

Original languageEnglish (US)
Pages (from-to)179-198
Number of pages20
JournalJournal of Complexity
Volume10
Issue number2
DOIs
StatePublished - Jun 1994

Fingerprint Dive into the research topics of 'One-way communication complexity of computing a collection of rational functions'. Together they form a unique fingerprint.

Cite this