Publications [#237084] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH, ON SYNCHRONOUS PARALLEL COMPUTATIONS WITH INDEPENDENT PROBABILISTIC CHOICE., SIAM Journal on Computing, vol. 13 no. 1 (January, 1984), pp. 46-56, Society for Industrial & Applied Mathematics (SIAM) [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. The computational complexity of time, space, and processor bounded probabilistic parallel RAMs is characterized in terms of the computational complexity of probabilistic sequential RAMs. It is shown that parallelism uniformly speeds up time bounded probabilistic sequential RAM computations by nearly a quadratic factor. It is also shown that probabilistic choice can be eliminated from parallel computations by introducing nonuniformity.