Carleton University
Technical Report TR-218
February 1993
A Time-Randomness Tradeoff for Selection in Parallel
Danny Krizanc
Abstract
In this paper we study the problem finding the median on a parallel comparison tree (PCT). Results due to Valiant [Va], Meggido [Me] and Reishcuk [Re] show a provable gap between the randomized and deterministic parallel complexity of selection. We prove a tight tradeoff between the amount of randomness used by an algorithm for this problem and its performance, measured by the time it requires to complete its computation with a given failure probability. The tradeoff provides a smooth bridge between the deterministic and randomized complexity of the problem.