1.
John H. Reif,
Parallel Interpolation Search. 23rd
Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, October 1985. Published
as D.E. Willard and John H. Reif, Parallel Processing can be Harmful: the
Unusual Behavior of Interpolation Search, Journal
of Information and Computation, Vol. 81, No. 3, June 1989, pp. 364-379. [PDF]
2. R. Paturi, S. Rajasekaran, and John H. Reif,
Efficient and Robust Learning Using Statistical Bootstrap, Proceedings of the 2nd Annual Workshop on Computational Learning Theory, Santa Cruz, CA, August 1989. [PostScript] [PDF] Published
as The Light Bulb Problem, Information
and Computation, 117(2):187-192, March 1995. [PDF]
3. R. Paturi, S. Rajasekaran, and John H. Reif,
Efficient and Robust Learning Using Statistical Bootstrap, Workshop on Computational Learning Theory, Santa Cruz, CA, August
1989. Published as The Light Bulb Problem, Information
and Computation, 117(2):187-192, March 1995. [PostScript] [PDF] journal: [PDF]
4. M. Kao, John H. Reif, and S. Tate, Searching in an
Unknown Environment: An Optimal Randomized Algorithm for the Cow-Path Problem, Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'93), Austin,
TX, Jan 1993, pp.441-447. Published in Information
and Computation, Vol 131, No. 1 (1996), p 63-80. [PostScript] [PDF] or [PostScript]
5. S. Chen and John H. Reif, Fast Pattern Matching for
Entropy Bounded Text. Proceedings: IEEE
Data Compression Conference (DCC'95) Snowbird, UT, IEEE
Computer Society Press, James A. Storer, Martin Cohn (Eds.), March 1995, pp. 282-301. [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 S. 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. [PostScript]
[PDF]