Tradeoffs between communication and space

Abstract

This paper initiates the study of communication complexity when the processors have limited work space. The following tradeoffs between number C of communications steps and space S are proved: (1) For multiplying two n×n matrices in the arithmetic model with two-way communication, CS = Θ(n3). (2) For convolution of two degree n polynomials in the arithmetic model with two-way communication, CS = Θ(n2). (3) For multiplying an n × n matrix by an n-vector in the Boolean model with one-way communication, CS = Θ(n2).