Elron Bandel, Yotam Perlitz, et al.
NAACL 2024
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.
Elron Bandel, Yotam Perlitz, et al.
NAACL 2024
Annina Riedhauser, Viacheslav Snigirev, et al.
CLEO 2023
Rocco Langone, Carlos Alzate, et al.
SSCI 2013
Gang Liu, Michael Sun, et al.
ICLR 2025