Bit Complexity of Order Statistics on a Distributed Star Network

Ornan Ori Gerstel, Yishay Mansour, Shmuel ZaksInf. Process. Lett 1989 · OpenReview

Abstract

We study the bit complexity of order statistics problem on an asynchronous distributed star network. We prove a lower bound of Ω(N log( L N )) bits for the k-selection problem, and lower bounds of Ω(N log(L − N)) bits for the problems of sorting and ranking. For each of the problems we introduce an algorithm that achieves that bound, thus showing all bounds to be optimal.
BibTeX
@inproceedings{gerstel1989bit,
  author = {Ornan Ori Gerstel and Yishay Mansour and Shmuel Zaks},
  title = {{Bit Complexity of Order Statistics on a Distributed Star Network}},
  booktitle = {Inf. Process. Lett},
  year = {1989},
  url = {https://openreview.net/forum?id=Q4M7dpkNaN},
}

Loading related content...

Figure