Kazuaki Ishizaki, Takeshi Ogasawara, et al.
VEE 2012
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. © 1987, ACM. All rights reserved.
Kazuaki Ishizaki, Takeshi Ogasawara, et al.
VEE 2012
Zhikun Yuen, Paula Branco, et al.
DSAA 2023
Hong Guan, Saif Masood, et al.
SoCC 2023
Erik Altman, Jovan Blanusa, et al.
NeurIPS 2023