Bit Complexity of Order Statistics on a Distributed Star Network
Lists
Only you see this
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...