1.
Leslie G. Valiant and
John H. Reif, A Logarithmic Time Sort for Linear Size Networks. 15th Annual
ACM Symposium on Theory of Computing,
Boston, MA, April 1983, pp. 10-16.
[PDF]
Published in Journal of the ACM(JACM), Vol. 34, No. 1,
January 1987, pp. 60-76. [PDF]
2.
John H. Reif, An n1+epsilon
Processor, 0(log n) Time Probabilistic Sorting Algorithm. SIAM 2nd
Conference on the Applications of Discrete Mathematics, Cambridge,
MA, June 1983, pp. 27-29. [PDF]
3. Sanguthevar Rajasekaran and John H. Reif, An
Optimal Parallel Algorithm for Integer Sorting. 26th Annual IEEE Symposium
on Foundations of Computer Science,
Portland, OR, October 1985, pp.
496-503. Published as Optimal and Sublogarithmic Time Randomized Parallel
Sorting Algorithms, SIAM Journal on Computing, Vol. 18, No. 3, June 1989, pp. 594-607. [PDF] or [PostScript] [PDF]
4. W.L. Hightower, J. Prins, and John H. Reif, Implementations
of Randomized Sorting on Large Parallel Machines. 4th Annual ACM Symposium
on Parallel Algorithms and Architectures (SPAA'92), San Diego, CA, pp. 158-167, July 1992. [PDF]
5. Sefeng Chen and John H. Reif, Using difficulty of
prediction to decrease computation: fast sort, priority queue and convex hull
on entropy bounded inputs, 34th Annual IEEE Conference on Foundations of
Computer Science (FOCS '93) Proceedings, November 1993, Palo Alto, CA, pp. 104-112. [PDF]