tradeoffs between communication and space
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: For multiplying two n  n matrices in the arithmetic model with two-way communication, CS = &THgr;( n 2 ). For convolution of two degree n polynomials in the arithmetic model with two-way communication, CS = &THgr;( n 2 ). For multiplying an n  n matrix by an n -vector in the Boolean model with one-way communication, CS = &THgr;( n 2 ). In contrast, the discrete Fourier transform and sorting can be accomplished in &Ogr; ( n ) communication steps and &Ogr; (log n ) space simultaneously, and the search problems of Karchmer and Wigderson associated with any language in NC k can be solved in &Ogr; (log k n ) communication steps and &Ogr; (log k n ) space simultaneously.
communication space paper communication complexity processor model polynomial transformation sorting log search association language vectorization