Publications [#330502] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Rajasekaran, S; Reif, JH, Randomized parallel computation, Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 278 LNCS (January, 1987), pp. 364-376, Springer Berlin Heidelberg (Lecture Notes in Computer Science, Vol. 278, 1987, pp. 364-376.) [pdf], [doi]
   (last updated on 2026/01/14)

   Abstract:
   This paper surveys randomized parallel algorithms found in the literature for various problems in computer science. In particular we will demonstrate the power of randomization as a tool for parallelizing sequential algorithms and introduce the reader to some of the techniques employed in designing randomized parallel algorithms. We consider representative problems from the following areas of computer science and describe how randomized parallel algorithms for these problems have been obtained: 1)routing and sorting, 2)processor load balancing, 3)algebra, and 4)graph theory. Finally we discuss methods of derandomizing randomized parallel algorithms.