Name
Abstract | ||
|---|---|---|
The main result of this paper is a general technique for determining lower bounds on the communication complexity of problems on various distributed computer networks. This general technique is derived by simulating the general network by a linear array and then using a lower bound on the communication complexity of the problem on the linear array. Applications of this technique yield optimal bounds on the communication complexity of merging, ranking, uniqueness, and triangle-detection problems on a ring of processors. Nontrivial near-optimal lower bounds on the communication complexity of distinctness, merging, and ranking on meshes and complete binary trees are also derived. |
Year | DOI | Venue |
|---|---|---|
1987 | 10.1145/31846.32978 | J. ACM |
Keywords | Field | DocType |
lower bound,linear array,commuication complexity,communication complexity,communicaton complexity,conmunication complexity,distinctness problem,near optimal,p time,boolean function,Communication Complexity,Computer Networks,Lower Bounds | Boolean function,Uniqueness,Discrete mathematics,Combinatorics,Polygon mesh,Ranking,Computer science,Algorithm,Communication complexity,Distributed algorithm,Intelligent Network,Worst-case complexity | Journal |
Volume | Issue | ISSN |
34 | 4 | 0004-5411 |
Citations | PageRank | References |
25 | 2.46 | 17 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prasoon Tiwari | 1 | 592 | 96.81 |