1.
John H. Reif, The
Very Unusual Behavior of 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, 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]