Papers by Reif on Randomized Parallel Algorithms (6 papers)


1. John H. Reif, On the Power of Probabilistic Choice in Synchronous Parallel Machines. Harvard University TR-30-81. 9th International Colloquium on Automata, Languages and Programming, Aarhus, Denmark, 1982, pp. 442-450. Published as On Synchronous Parallel Computations with Independent Probabilistic Choice in SIAM Journal on Computing, Vol. 13, No. 1, February 1984, pp. 46-56. [PDF]


2. Sanguthevar Rajasekaran and John H. Reif, Randomized Parallel Computation. Presented at Foundations of Computation Theory Conference, Kasan, USSR, June 1987; Lecture Notes in Computer Science, Vol. 278, 1987, pp. 364-376. Published in Chapter 11 of Concurrent Computations: Algorithms, Architecture and Technology, S.K. Tewksbury, B.W. Dickinson and S.C. Schwartz, ed., 1988, pp. 181-202. [PDF]


3. John H. Reif and Doug Tygar, Efficient Parallel Pseudo-random Number Generation. CRYPTO-85, Proceedings, Vol. 218, H. Williams and E. Brickell, ed., Springer-Verlag, New York, NY, 1986, pp. 433-446 Presented at the Mathematical Theory of Security, Boston, MA, 1985. Published in SIAM Journal on Computing, Vol. 17, No. 2, April 1988, pp. 404-411. [PDF]


4. John H. Reif, Efficient Parallel Algorithms: Theory and Practice. SIAM 35th Anniversary Meeting, Denver, CO, October 1987. XI World Computer Congress, IFIP 89, San Francisco, CA, 1989.


5. John H. Reif and Sandeep Sen, Randomized Parallel Algorithms. IBM Workshop on Capabilities and Limitations of Parallel Computing, San Jose, CA, December 1988. Information Processing 89, G. Ritter, ed., Elsevier Science Publishers, North Holland, 1989, pp. 455-458. [PDF] A Case for Randomized Parallel Algorithms in Opportunities and Constraints of Parallel Computing, J.L.C. Sanz (ed.), Springer-Verlag New York, 1989, pp. 101-105. Also presented as Randomization in Parallel Algorithms and its Impact on Computational Geometry, in Optimal Algorithms;Lecture Notes in Computer Science, Vol. 401, 1989, pp. 1-8. [PDF] Also presented as C. Pandurangan S. Rajasekaran John H. Reif S. Sen, Studies on Sequential and Parallel Randomized Algorithms, Indo-US Workshop on Cooperative Research in Computer Science, Bangalore, India, August 4-6, 1992. [PDF]


6. John H. Reif, Probabilistic Algorithms in Group Theory. Foundations of Computation Theory (FCT85), Cottbus, Democratic Republic of Germany, September 1985; appeared in Lecture Notes in Computer Science, Vol. 199, 1985, pp. 341-350. Also TR85-01, Dept. of Computer Science, Harvard University, (1985). Published as Selman Azhar and John H. Reif, Efficient Algorithmic Learning of the Structure of Permutation Groups by Examples, Computers & Mathematics with Applications, Volume 37, Issue 10, May 1999, pp. 105-132. [PDF]