Name
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:For multiplying two n × n matrices in the arithmetic model with two-way communication, CS = &THgr;(n2).For convolution of two degree n polynomials in the arithmetic model with two-way communication, CS = &THgr;(n2).For multiplying an n × n matrix by an n-vector in the Boolean model with one-way communication, CS = &THgr;(n2).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 NCk can be solved in &Ogr;(logk n) communication steps and &Ogr;(logk n) space simultaneously. |
Year | DOI | Venue |
|---|---|---|
1989 | 10.1145/73007.73028 | STOC |
Keywords | Field | DocType |
discrete fourier transform,communication complexity,boolean model | Binary logarithm,Discrete mathematics,Combinatorics,Polynomial,Convolution,Matrix (mathematics),Boolean model,Communication complexity,Sorting,Discrete Fourier transform,Mathematics | Conference |
ISBN | Citations | PageRank |
0-89791-307-8 | 8 | 2.61 |
References | Authors | |
19 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tak-Wah Lam | 1 | 1860 | 164.96 |
| Prasoon Tiwari | 2 | 592 | 96.81 |
| Martin Tompa | 3 | 1103 | 149.69 |