Publications [#331476] of John H. Reif

Conference articles PUBLISHED

1. Reif, JH, On the power of probabilistic choice in synchronous parallel computations, Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 140 LNCS (January, 1982), pp. 442-450, Springer Verlag, ISBN 9783540115762 [doi]
   (last updated on 2026/01/14)

   Abstract:
   This paper introduces probabilistic choice to synchronous parallel machine models; in particular parallel RAMs. The power of probabilistic choice in parallel computations is illustrated by parallelizing some known probabilistic sequential algorithms. We characterize the computational complexity of time, space, and processor bounded probabilistic prallel RAMs in terms of the computational complexity of probabilistic sequential RAMs. We show that parallelism uniformly speeds up time bounded probabilistic sequential RAM computations by nearly a quadratic factor. We also show that probabilistic choice can be eliminated from parallel computations by introducing nonuniformity.