1. John H.
Reif (Editor), VLSI Algorithms and Architectures, 3rd Aegean Workshop on
Computing, AWOC 88, Corfu, Greece, June 28 - July 1
1988, 476 pages, Springer-Verlag Lecture Notes in Computer Science, Vol. 319 (1988).

2. John H.
Reif (Editor), Synthesis of Parallel Algorithms, 22 chapters, 1011 pages. Kluwer Academic
Publishers, San Mateo, California,
1993.

3. Robert
Paige, John H. Reif, and Ralph Wachter (Editors), Parallel Algorithm Derivation and Program
Transformation, 228 pages.
Published by Kluwer Academic Publishers, 1993.

4.
Sanguthevar Rajasekaran, pp. M. Pardalos, John H. Reif and J. Rolim (Editors), Handbook
of Randomized Computing (Edited
by), Kluwer Volume I and II, Academic Press, London, 2001.

5.
Proceedings of the 34th ACM Symposium on Theory of
Computing (STOC2002), (Edited by John
H. Reif), Montréal, Québec, Canada, May 19-21, 2002.
Also, John H. Reif, Guest
Editor, Special Issue of Selected Papers from Proceedings of the Thirty-Fourth
Annual ACM Symposium on Theory of Computing (STOC2002) Journal of Computer and
System Sciences(JCSS), Volume 67, Issue 2, Page 211, (September 2003). Guest Editor’s Foreword, Page 211. [PDF]

6. Junghuei Chen and John H. Reif (Editors),
Proceedings of the Ninth International Meeting on DNA
Based Computers (DNA9), Madison, Wisconsin, June 1-3, 2003, 225 pages, Lecture Notes in Computer Science Vol.
2943, Springer-Verlag, New York, (2004).

7. John H.
Reif (Editor), Proceedings of the First Conference on Foundations of
Nanoscience: Self-Assembled Architectures and Devices(FNANO04), Snowbird, Utah,
(April 21-23, 2004), Published by Sciencetechnica (2004). Editor’s Foreword [PDF]

8. John H.
Reif (Editor), Proceedings of the Second Conference on Foundations of
Nanoscience: Self-Assembled Architectures and Devices(FNANO05), Snowbird, Utah,
(April 24-28, 2005), Published by Sciencetechnica (2005). Editor’s Foreword [PDF]

9. John H.
Reif (Editor), Proceedings of the Third Conference on Foundations of
Nanoscience: Self-Assembled Architectures and Devices(FNANO06), Snowbird, Utah,
(April 23-27, 2006), Published by Sciencetechnica (2006).

10. John H.
Reif (Editor), Proceedings of the Fourth Conference on Foundations of
Nanoscience: Self-Assembled Architectures and Devices(FNANO07), Snowbird, Utah,
(April 18-22, 2007), Published by Sciencetechnica (2007).

11. Sanguthevar Rajasekaran
and John H. Reif (Editors), Handbook of Parallel Computing: Models, Algorithms
and Applications, Published by
Taylor & Francis, Boca Raton, FL. ISBN 978-1584886235
(December, 2007). [PDF]

12. John H.
Reif (Editor), Proceedings of the Fifth Conference on Foundations of
Nanoscience: Self-Assembled Architectures and Devices(FNANO08), Snowbird, Utah,
(April 21-25, 2008), Published by Sciencetechnica (2008).

13. John H.
Reif and Marya Lieberman, editors, Proceedings of the Sixth Conference on
Foundations of Nanoscience: Self-Assembled Architectures and Devices(FNANO09),
Snowbird, Utah, Published by Sciencetechnica (April 20-24, 2009).

14. Sudheer
Sahu and John H. Reif, DNA-based Self-assembly and Nanorobotics, Published by VDM Verlag, Dr. Mueller e.K.,
Saarbrücken, Germany, 128 pages, (November 10, 2008) ISBN-10: 363909770X,
ISBN-13: 978-3639097702.

15. John H.
Reif and Marya Lieberman, editors, Proceedings of the Seventh Conference on
Foundations of Nanoscience: Self-Assembled Architectures and Devices(FNANO10),
Snowbird, Utah, Published by Sciencetechnica (April 27-30, 2010).

16. John H.
Reif and Marya Lieberman, editors, Proceedings of the Eighth Conference on
Foundations of Nanoscience: Self-Assembled Architectures and Devices(FNANO11),
Snowbird, Utah, Published by Sciencetechnica, (April 11-15, 2011).

John H. Reif
and Marya Lieberman, editors, Proceedings of the Ninth Conference on
Foundations of Nanoscience: Self-Assembled Architectures and Devices(FNANO12),
Snowbird, Utah, Published by Sciencetechnica, (April 16-19, 2012).

**Papers
**(most are downloadable)

1. John H. Reif, Combinatorial Aspects of Symbolic Program Analysis.
Ph.D. Thesis, Harvard University, July 1977. [PDF]
(Preface & Introductory Chapter 1:[PDF],
Chapter 2(pub. #3):[PDF],
Chapter 3:[PDF],
Chapter 4(pub. #5):[PDF],Chapter
5(pub. #4):[PDF])

2. Richard Barakat and John H. Reif, Numerical Solution of the
Fokker-Plank Equation via Chebyschev Approximations with Reference to First
Passage Time Probability Functions. *Journal
of Computational Physics*, Vol. 23, No. 4, April 1977, pp. 425-445. [PDF]

3. John H. Reif and Harry R. Lewis, Symbolic Evaluation and the Global
Value Graph. *4th ACM Symposium on
Principals of Programming Languages*,* *Los
Angeles, CA, January 1977, pp. 104-118. [PDF]
Published as Efficient Symbolic Analysis of Programs, in *Journal of Computer and System Sciences*,* *Vol. 32, No. 3, June 1986, pp. 280-314. [PDF]

4. John H. Reif, Code Motion. Presented at *Conference on Theoretical Computer Science*,* *University of Waterloo, Canada, 1977. Published in *SIAM Journal on Computing*, Vol. 9, No.
2, May 1980, pp. 375-395. [PDF]

5. John H. Reif, Symbolic Program Analysis in Almost Linear Time. *5th Annual ACM Symposium on Principals of
Programming Languages*, Tucson, AZ, January 1978, pp. 76-83. [PDF]
Published as John H. Reif and R.E. Tarjan, *SIAM
Journal on Computing*, Vol. 11, No. 1, February 1982, pp. 81-93. [PDF]

6. John H. Reif, Data Flow Analysis of Communicating Processes. *6th Annual ACM Symposium on Principals of
Programming Languages*,* *San
Antonio, TX, January 1979, pp. 257-268. [PDF]
Published as John H. Reif and Scott A. Smolka, *International Journal of Parallel Programming*, Vol. 19, No. 1,
February 1990. [PDF]

7. John H. Reif, The Complexity of Extending a Graph Imbedding.
Computer Science Department, University of Rochester, TR-42, October 1978. [PDF]

8. Ion S. Filotti,
Gary Miller, and John H. Reif, On Determining the Genus of a Graph in 0(v^0(g))
Steps, *11th Annual ACM Symposium on
Theory of Computing(STOC79)*, Atlanta, GA, April 1979, pp. 27-37. [PDF]

9. John H. Reif, Universal Games of Incomplete Information. *11th Annual ACM Symposium on Theory of
Computing*, Atlanta, GA, April 1979, pp. 288-308. Harvard University
TR-35-81. [PDF]
Published as The Complexity of Two-Player Games of Incomplete Information. *Journal of Computer and System Sciences*,
Vol. 29, No. 2, October 1984, pp. 274-301. [PDF]

10. Gary L.
Peterson and John H. Reif, Multiple-Person Alternation. *20th Annual IEEE Symposium on Foundations of Computer Science*, San
Juan, Puerto Rico, October 1979, pp. 348-363. Published as Gary L. Peterson,
John H. Reif, and Selman Azhar, Lower Bounds for Multiplayer Noncooperative
Games of Incomplete Information, Computers and Mathematics with Applications,
Volume 41, April 2001, pp. 957-992. [PDF]

11. John H. Reif, Complexity of the Mover's Problem and
Generalizations. *20th Annual IEEE
Symposium on Foundations of Computer Science*, San Juan, Puerto Rico,
October 1979, pp. 421-427. [PDF]
Published as Complexity of the Generalized Mover's Problem, Chapter 11 in *Planning, Geometry and Complexity of Robot
Motion*, Jacob Schwartz, ed., Ablex Pub., Norwood, NJ, 1987, pp. 267-281. [PDF]

12. Gary L. Peterson and John H. Reif, A Dynamic Logic of
Multiprocessing with Incomplete Information. *7th Annual ACM Symposium on Principles of Programming Languages*,* *Las Vegas, NV, January 1980, pp.
193-202. [PDF]

13. John H. Reif, Logics for Probabilistic Programming. *12th Annual ACM Symposium on Theory of
Computing*,* *Los Angeles, CA, April
1980, pp. 8-13. [PDF]

14. John H. Reif and Paul G. Spirakis, Random Matroids. *12th Annual ACM Symposium on Theory of
Computing*,* *Los Angeles, CA, April
1980, pp. 385-397. Revised as Probabilistic Analysis of Random
Extension-Rotation Algorithms, Harvard University TR-28-81, 1980. [PDF]

15. John H. Reif and Paul G. Spirakis, Distributed Algorithms for
Synchronizing Interprocess Communication Within Real Time. *13th Annual ACM Symposium on Theory of Computing*,* *Milwaukee, WI, 1981, pp. 133-145.
Published as Real-Time Synchronization of Interprocess Communications: *ACM Journal of Transactions on Programming
Languages and Systems*, Vol. 6, No. 2, April 1984, pp. 215-238. [PDF]

16. John H. Reif, Minimum s-t Cut of Planar Undirected Network in 0(n
log^2n) Time, 8th Colloquium on Automata, Languages and Programming, (Shimon
Even and Oded Kariv, editors) volume 115 of Lecture Notes in Computer Science,
pp. 56-67, Acre (Akko), Israel, 13-17 July 1981. Springer-Verlag. Published in *SIAM Journal on Computing*, Vol. 12, No.
1, February 1983, pp. 71-81. [PDF]

17. John H. Reif, Symmetric Complementation. *14th Annual ACM Symposium on Theory of Computing*,* *San Francisco, CA, May 1982, pp.
201-214. Presented at the NSF/AMS on *Probabilistic
Computational Complexity*,* *Durham,
NH, June 1982. Published in *Journal of
the ACM(JACM)*,* *Vol. 31, No. 2,
April 1984, pp. 401-421. [PDF]

18. Joseph Y. Halpern and John H. Reif, The Propositional Dynamic
Logic of Deterministic, Well-Structured Programs, *22nd Annual IEEE Symposium on Foundations of Computer Science*,* *Nashville, TN, October 1981, pp.
322-334. Published in *Journal of
Theoretical Computer Science*,* *Vol.
27, 1983, pp. 127-165. [PDF]

19. John H. Reif and Paul G. Spirakis, Unbounded Speed Variability in
Distributed Communication Systems. *9th
Annual ACM Symposium on Principals of Programming Languages(POPL80)*,* *Albuquerque, NM, January 1982, pp.
46-56. [PDF]
Published in *SIAM Journal on Computing*,* *Vol. 14, No. 1, February 1985, pp.
75-92. [PDF]

20. Gary L. Peterson and John H. Reif, Decision Algorithms for
Multiplayer Games of Incomplete Information. Harvard University, TR-34-81.
Published as Gary L. Peterson, John H. Reif, and Selman Azhar, Decision
Algorithms for Multiplayer Non-Cooperative Games of Incomplete Information.
Computers and Mathematics with Applications, Vol. 43, Jan. 2002, pp. 179-206. [PDF]

21. John H. Reif and Paul G. Spirakis, K-connectivity in Random
Undirected Graphs, *Discrete Mathematics*,* *Vol. 54, No. 2, April 1985, pp.
181-191. [PDF]
(Also, John H. Reif and Paul G. Spirakis, Strong k-connectivity in Digraphs and
Random Digraphs, Harvard University TR-25-81. [PDF])

22. John H. Reif and Paul G. Spirakis, Strong k-connectivity in
Digraphs and Random Digraphs, Harvard University TR-25-81. [PDF]

23. 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]

24. John H. Reif and Paul G. Spirakis, Real Time Resource Allocation
in Distributed Systems, *ACM Symposium on
Principals of Distributed Computing*,* *Ottawa,
Canada, August 1982, pp. 84-94. [PDF]

25. John H. Reif, Parallel Time *0*(log
*n*) Time Acceptance of Deterministic
CFLs. *23rd Annual IEEE Symposium on
Foundations of Computer Science*,* *Chicago,
IL, November 1982, pp. 290-296. Published as Phlip Klein and John H. Reif,
Parallel Time *0*(log *n*) Time Acceptance of Deterministic CFLs
on an Exclusive-Write P-RAM, *SIAM Journal
on Computing*,* *Vol. 17, No. 3,
June 1988, pp. 463-485. [PDF]

26. John H. Reif and Paul G. Spirakis, Expected Parallel Time and
Sequential Space Complexity of Graph and Digraph Problems, *Algorithmica*, Special Issue on Graph Algorithms, Vol. 7, Numbers 5
& 7, pp. 597-630, 1992. [PDF]

27. 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]

28. John H. Reif and W.L. Scherlis, Deriving Efficient Graph Algorithms. Logics of Programs Workshop, Carnegie-Mellon
University, Pittsburgh, PA, June 1983, Lecture Notes in Computer Science, Vol.
164, 1984, pp. 421-441. Published in: Verification: Theory and Practice: Essays
Dedicated to Zohar Manna on the Occasion of His 64th Birthday (edited by Nachum
Dershowitz), LNCS series Vol. 2772, pp. 645-681, 2004. [PDF]
or [PDF]

29. John H. Reif and A.P. Sistla, A Multiprocess Network Logic with
Temporal and Spatial Modalities, *10th
International Colloquium on Automata, Languages and Programming*, Barcelona,
Spain, July 1983; *Lecture Notes in
Computer Science*, Vol. 154, 1983, pp. 629-639. Published in *Journal of Computer and System Sciences*,* *Vol. 30, No. 1, February 1985, pp.
41-53. [PDF]

30. John H. Reif, Logarithmic Depth Circuits for Algebraic Functions. *24th Annual IEEE Symposium on Foundations of
Computer Science*, Tucson, AZ, November 1983, pp. 138-145. Published in *SIAM Journal on Computing*,* *Vol. 15, No. 1, February 1986, pp.
231-242. [PDF]

31. 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]

32. John H. Reif, Probabilistic Parallel Prefix Computation, *13th Annual International Conference on
Parallel Processing*,* *Michigan,
1984. Published in *Computers and
Mathematics with Applications*, Vol. 26, Number 1, July 1993, pp. 101-110. [PDF]

33. John H. Reif and Paul G. Spirakis, Probabilistic Bidding Gives
Optimal Distributed Resource Allocation. *11th
International Colloquium on Automata, Languages and Programming*,* *Antwerp, Belgium, July 1984. Published
in *Lecture Notes in Computer Science*,
Vol. 172, pp. 391-402. [PDF]

34. John H. Reif, Depth-First Search is Inherently Sequential. *Information Processing Letters*,* *Vol. 20, No. 5, June 12, 1985, pp.
229-234. [PDF]

35. John H. Reif, A Topological Approach to Dynamic Graph Connectivity.
*Information Processing Letters*,* *Vol. 25, No. 1, April 20, 1987, pp.
65-70. [PDF]

36. Gautam Kar, Christos N. holaou, and John H. Reif, Assigning
Processes to Processors: A Fault-Tolerant Approach, *14th International Conference on Fault-Tolerant Computing*,* *Kissimmee, FL, June 1984, pp. 306-309.
[PDF]

37. Micheal Ben-Or, Dextor Kozen, and John H. Reif, The Complexity of
Elementary Algebra and Geometry. *16th Annual
Symposium on Theory of Computing*, Washington, DC, April-May 1984,* *pp. 457-464. [PDF]
Published in *Journal of Computer and
Systems Sciences*,* *Vol. 32, No. 2,
April 1986, pp. 251-264. [PDF]

38. Ravi Nair, Anni Bruss, and John H. Reif, Linear Time Algorithms
for Optimal CMOS Layout, *International
Workshop on Parallel Computing and VLSI*, Amalfi, Italy, May 1984; *VLSI: Algorithms and Architectures*,* *North-Holland, pp. 327-338. [PDF]

39. 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]

40. Peter Gacs and John H. Reif, A Simple Three-dimensional Real-time
Reliable Cellular Array. *17th Annual ACM
Symposium on Theory of Computing*, Providence, RI, May 1985, pp. 388-395. [PDF]
Published in *Journal of Computer and
System Sciences*,* *Vol. 36, No. 2,
April 1990, pp. 125-147. [PDF]

41. Victor Y. Pan and John H. Reif, Efficient Parallel Solution of
Linear Systems. *17th Annual ACM Symposium
on Theory of Computing(STOC85)*, Providence, RI, (ACM Press, New York) May
1985,* *pp. 143-152. Presented at the
meeting on Efficient Algorithms, Mathematisches Forschungsinstitut,
Oberwolfach, W. Germany, November 1984. Presented at *2nd SIAM Conference on Applied Linear Algebra*, Raleigh, NC, April
1985. Published as Fast and Efficient Parallel Solution of Sparse Linear
Systems. *SIAM Journal on Computing*,
Vol 22, No. 6, pp. 1227-1250, December 1993. [PDF]
or [PDF]

42. Gary Miller and John H. Reif, Parallel Tree Contraction and its
Application. Harvard University TR-18-85. *26th
Annual IEEE Symposium on Foundations of Computer Science*, Portland, OR,
October 1985, pp. 478-489.

42a Portions
Published as Parallel Tree Contraction Part I: Fundamentals, Parallel Tree Contraction Part 1: Fundamentals. In
Randomness and Computation, (*Advances
in Computing Research*, Vol. 5., Silvio Micali,
editor), pp. 47–72, JAI Press, Greenwich,
Connecticut, 1989. [PDF]

42b Portions
Published as Parallel Tree Contraction Part II: Further Applications, *SIAM Journal on Computing*, Vol. 20, No.
6, pp. 1128-1147, December 1991. [PDF]

43. 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]

44. John H. Reif and M. Sharir, Motion Planning in the Presence of
Moving Obstacles, *26th Annual IEEE
Symposium on Foundations of Computer Science*, Portland, OR, October 1985,* *pp. 144-154. Published in Journal of
the ACM (*JACM)*, 41:4, July 1994, pp.
764-790. [PDF]
or [PostScript]
[PDF]

45. John H. Reif, Probabilistic Algorithms in Group Theory.
Foundations of Computation Theory (FCT85), Cottbus, Democratic Republic of
Germany, September 1985; *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]

46. Victor Y. Pan and John H. Reif, Fast and Efficient Algorithms for
Linear Programming and for the Linear Least Squares Problem, *12th International Symposium on Mathematical
Programming*,* *MIT, Cambridge, MA,
pp. 283-295, August 1985. Abstract published as Efficient Parallel Linear
Programming, *Operations Research Letters*,* *Vol. 5, No. 3, August 1986, pp.
127-135. [PDF] Also presented as Fast and Efficient Parallel
Linear Programming and Least Squares Computations at Aegean Workshop on
Computing, Loutraki, Greece, July 1986; *Lecture
Notes in Computer Science*, Springer-Verlag, Vol. 227, 1986, pp. 283-295.
Full Paper published as Fast and Efficient Linear Programming and Linear
Least-Squares Computations, *Computers and
Mathematics with Applications*,* *Vol.
12A, No. 12, 1986, pp. 1217-1227. [PDF]

47. 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]

48. John H. Reif and Scott A. Smolka, The Complexity of Reachability
in Distributed Communicating Processes, *Journal
of Acta Informatica*,* *Vol. 25(3),
April 1988, pp.333-354. [PDF]

49. Steve Homer and John H. Reif, Arithmetic Theories for
Computational Complexity Problems, *Journal
of Information and Control*, Vol. 69, nos. 1-3, April/May/June 1986, pp.
1-11. [PDF]

50. James A. Storer and John H. Reif, A Parallel Architecture for High
Speed Data Compression,* 3rd Symposium on
the Frontiers of Massively Parallel Computation*, College Park, MD, October
1990, pp. 238-243. Published in Journal of Parallel and Distributed
Computation, No. 13, 1991, pp. 222-227. [PDF]

51. Victor Y. Pan and John H. Reif, Fast and Efficient Parallel Solution
of Dense Linear Systems. *Computers and
Mathematics with Applications*, Vol. 17, No. 11, 1989, pp. 1481-1491. [PDF]

52. John H. Reif and James A. Storer, Shortest Paths in the plane with
polygonal obstacles, *Journal of the
ACM(JACM)* 41:5, September, 1994, pp. 982-1012. [PDF]

53. John H. Reif and James A. Storer, Minimizing Turns for Discrete
Movement in the Interior of a Polygon, *IEEE
Journal of Robotics and Automation*,* *Vol.
3, No. 3, June 1987, pp. 182-193. [PDF]

54. John H. Reif, Efficient VLSI Fault Simulation. *Computers and Mathematics with Applications*,
Vol 25, No. 2, Jan. 1993, pp. 15-32. [PDF]

55. Richard E. Ladner and John H. Reif, The Logic of Distributed Protocols.
*Conference on Theoretical Aspects of
Reasoning about Knowledge*, Los Altos, CA, March 1986, pp. 207-223. [PDF]

56. Victor Y. Pan and John H. Reif, Extension of the Parallel Nested
Dissection Algorithm to Path Algebra Problems. Presented at *6th Conference on Foundation of Software
Technology and Theoretical Computer Science*,* *New Delhi, India; *Lecture
Notes in Computer Science*, Springer Verlag, Vol. 241, pp. 470–487, 1986. An
abstract of this paper appears as Parallel Nested Dissection for Path Algebra
Computations, *Operations Research Letters*,* *Vol. 5, No. 4, October 1986,
pp. 177-184. [PDF]
Published as Fast and Efficient Solution of Path Algebra Problems, *Journal of Computer and Systems Sciences*,
Vol. 38, No. 3, June 1989, pp. 494-510. [PDF]

57. John Canny and John H. Reif, New Lower Bound
Techniques for Robot Motion Planning Problems. *28th Annual IEEE Symposium on Foundations of Computer Science*,* *Los
Angeles, CA, October 1987, pp. 49-60. [PDF]

58. Richard Barakat and John H. Reif, Lower Bounds on the
Computational Efficiency of Optical Computing Systems. *Journal of Applied Optics*,* *Vol.
26, No. 6, March 15, 1987, pp. 1015-1018. [PDF]

59. Richard Barakat and John H. Reif, Polynomial Convolution Algorithm
for Matrix Multiplication with Application for Optical Computing. Published in *Journal of Applied Optics*,* *Vol. 26, No. 14, July 15, 1987, pp.
2707-2711. [PDF]

60. John H. Reif, A Survey on Advances in the Theory of Computational
Robotics. Proceedings of the Fourth Workshop of Adaptive Systems Control
Theory, Princeton, NJ, 1986. Also as Chapter in Book: Adaptive and Learning
Systems: Theory and Applications, Princeton, NJ* (edited by *K.S. Narendra), Plenum Press, New York, NY, pp.
421--427 1986. [PDF]

61. Phlip Klein and John H. Reif, An Efficient Parallel Algorithm for
Planarity. *27th Annual IEEE Symposium on
Foundations of Computer Science*, Toronto, Canada, October 1986,* *pp.*
*465-477. Published in *Journal of
Computer and System Sciences*,* *Vol.
37, No. 2, October 1988, pp. 190-246. [PDF]

62. Charles E. Leiserson, J.P. Mesirov, L. Nekludova, S.M. Omohundro,
John H. Reif, and W. Taylor, Solving Sparse Systems of Linear Equations on the
Connection Machine. *Annual SIAM
Conference*, Boston, MA, July 1986. [PDF]

63. T. Opsahl and
John H. Reif, Solving Very Large, Sparse Linear Systems on Mesh-Connected
Parallel Computers. *First Symposium on
Frontiers of Scientific Computing*,* *NASA,
Goddard Space Flight Center, Greenbelt, MD, September 1986, pp. 2241-2248. [PDF]

64. John H. Reif,
Simon Kasif, and Deepak Sherlekar, Formula Dissection: A Parallel Algorithm for Constraint
Satisfaction. *IEEE Workshop on Computer
Architecture for Pattern Analysis and Machine Intelligence*, Seattle, WA,
October 1987, pp. 51-58. Published in Computers and Mathematics with
Applications, Vol. 5, (2008), pp. 1170-1177. [PDF] [PDF]

65. John H. Reif and Sandeep Sen, Optimal
Randomized Parallel Algorithms for Computational Geometry. *16th International Conference on Parallel Processing*, St. Charles,
IL, August 1987, pp. 270-276. Published in *Algorithmica*, Vol. 7, No. 1, January 1992, pp. 91-117. [PDF]

66. John Canny, B. Donald, John H. Reif and Patrick G. Xavier. On the
Complexity of Kinodynamic Planning. *29th
Annual IEEE Symposium on Foundations of Computer Science*,* *White Plains, NY, October 1988, pp.
306-316. Published as Kinodynamic Motion Planning, *Journal of the ACM*, Vol 40(5), November 1993, pp. 1048-1066. [PDF]

67. 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]

68. John H. Reif and Steve R. Tate, On Threshold Circuits and
Polynomial Computation. *2nd Structure in
Complexity Theory Conference*,* *Ithaca,
NY, June 1987. Published in *SIAM Journal
on Computing*, Vol.21, No. 5, October 1992, 896-908. [PDF] or
[PostScript]
[PDF]

69. Vijaya Ramachandran and John H. Reif, An Optimal Parallel
Algorithm for Graph Planarity. *30th
Annual IEEE Symposium on Foundations of Computer Science*, Research Triangle
Park, NC, October 1989, pp. 282-287. Published as Planarity Testing in Parallel*, Journal of Computer and System Sciences*,
**49**:3, December, 1994, pp. 517-561. [PostScript]
[PDF]

70. Sanguthevar Rajasekaran and John H. Reif, Nested Annealing: A
Provable Improvement to Simulated Annealing. Presented at *Workshop on Applications of Combinatorics and Graph Theory to Computer
Science*, Institute for Mathematics and its Applications, University of
Minnesota, December 1987. Presented at the *15th
International Colloquium on Automata, Languages and Programming*,* *Tampere, Finland, July 1988; *Lecture Notes in Computer Science*, Vol.
317, 1988, pp. 455-472. Published in *Journal
of Theoretical Computer Science*, 99(1):157-176, 1 June 1992. [PDF]

71. Victor Y. Pan and John H. Reif, Some Polynomial and Toeplitz
Matrix Computations. *28th Annual IEEE
Symposium on Foundations of Computer Science*, Los Angeles, CA, October
1987, (IEEE Computer Society Press)* *pp.
173-184. [PDF]

72. James A. Storer and John H. Reif, Real-time Compression of Video
on a Grid-connected Parallel Computer. *3rd International
Conference on Supercomputing*,* *Boston,
MA, May 1988. [PDF]

73. Edward W. Davis and John H. Reif, Architecture and Operation of the
BLITZEN Processing Element. *3rd International
Conference on Computing on Supercomputing*,* *Boston, MA, May 1988. Also revised as Donald W. Blevins, Edward W.
Davis, and John H. Reif, Processing Element and Custom Chip Architecture for
the BLITZEN Massively Parallel Processor, MCNC Technical Report TR87-22,
October 1987, revised June 1988. [PDF]

74. John H. Reif and Sandeep Sen, An Efficient Output-Sensitive
Hidden-Surface Removal Algorithm and its Parallelization. *4th Annual ACM Symposium on Computational Geometry*,* *Urbana, IL, June 1988,* *pp. 193-200. Published as An
Efficient Output-Sensitive Hidden-Surface Removal Algorithm for Polyhedral
Terrains, *Journal of Mathematical and
Computer Modeling*, Vol. 21, No. 5, pp. 89-104, 1995. [PDF]
or [PDF]

75. Lars S. Nyland and John H. Reif, An Algebraic Technique for
Generating Optimal CMOS Circuitry in Linear Time, *Computers and Mathematics with Applications *Vol 31, No. 1, Jan.
1996, pp.85-108. [PDF]

76. Donald W. Blevins, Edward W. Davis, Richard A. Heaton and John H.
Reif, BLITZEN: A Highly Integrated Massively Parallel Machine. *2nd Symposium on Frontiers of Massively
Parallel Computation*,* *Fairfax,
VA, October 1988. Published in *Journal of
Parallel and Distributed Computing*, Vol. 8, February 1990, pp. 150-160. [PDF]

77. John H. Reif and Steve R. Tate, Optimal Size Integer Division
Circuits. *21st Annual ACM Symposium on
Theory of Computing*, Seattle, WA, May 1989,* *pp. 264-273. Presented at meeting on Efficient Algorithms,
Mathematisches Forschungsinstitut, W. Germany, September 1989. Published in *SIAM Journal on Computing*, Vol. 19, No.
5, October 1990, pp. 912-924. [PDF]
or [PostScript]
[PDF]
or [PostScript]

78. John H. Reif and Sandeep Sen, Polling: A New Randomized Sampling
Technique for Computational Geometry, *21st
Annual ACM Symposium on Theory of Computing*, Seattle, WA, May 1989, pp.
394-404. [PDF]
Revised as Optimal Parallel Randomized Algorithms for Three-Dimensional Convex
Hulls and Related Problems, Published in *SIAM
Journal on Computing*, Vol. 21, No. 3, June 1992, pp. 466-485. [PDF]
or [PDF]
(see also Erratum: Optimal parallel randomized algorithms for three-dimensional
convex hulls and related problems. SIAM Journal on Computing, 23(2):447-448,
April 1994. [PDF])

79. John
H. Reif and A. Tyagi, Energy Complexity of Optical Computations, *2nd IEEE Symposium on Parallel and
Distributed Processing*, Dallas, TX, December 1990, pp. 14-21. Revised
for Journal Publication in International Journal of Unconventional
Computing, 2016, Vol. 12 Issue 5/6, pp. 393-412. [PDF]

80. John H. Reif, Optical expanders give constant time holographic
routing using O(N log N) switches, 1988 [PDF].
Full paper appeared as E.S. Maniloff, K. Johnson, and John H. Reif, Holographic
Routing Network for Parallel Processing Machines *Holographic Optics II: Principals and Applications*, G. Michael
Morris; Ed.* *SPIE Proceedings Series,
Vol. 1136, EPS/EUROPTICA/SPIE International Congress on Optical Science and
Engineering, Paris, France, April 1989, pp. 283-289. [PDF]

81. John H. Reif,
Doug Tygar, and Akitoshi Yoshida, The Computability and Complexity of Optical
Beam Tracing. *31st Annual IEEE Symposium
on Foundations of Computer Science*, St. Louis, MO, October 1990, pp.
106-114. Published as The Computability and Complexity of Ray Tracing in *Discrete & Computational Geometry*,
11: pp. 265-287 (December 1994). [PDF]

82. Selman Azhar,
Andrew McLennan and John H. Reif, Computation of Equilibria in Noncooperative
Games, Duke University Technical Report CS-1991-36. *Proc. Workshop for Computable Economics*, Dec. 1992. Published in Computers & Mathematics with Applications, Volume 50,
Issues 5-6, September 2005, pp. 823-854. [PDF]

83. R. Paturi, Sanguthevar 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]

84. 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, Sanguthevar Rajasekaran, John H. Reif,
Sandeep Sen, Studies on Sequential and Parallel Randomized Algorithms, Indo-US
Workshop on Cooperative Research in Computer Science, Bangalore, India, August
4-6, 1992. [PDF]

85. Victor Y. Pan and John H. Reif, On the Bit-Complexity of Discrete
Approximations to PDEs.* International
Colloquium on Automata, Languages, and Programming(ICALP 90)*, Warwich,
England, Springer Lecture Notes in Computer Science 443, pp. 612-625, July
1990. [PDF]
Published as The Bit-Complexity of Discrete Solutions of Partial Differential
Equations: Compact Multigrid, *Computers
and Mathematics with Applications,* Vol. 20, No. 2, 1990, pp. 9-16. [PDF].

86. John H. Reif and A. Tyagi, Efficient Algorithms for Optical
Computing with the DFT Primitive, Presented at *10th Conference on Foundations of Software Technology and Theoretical
Computer Science*, Bangalore, India, *Lecture
Notes in Computer Science, pp. 149-160 (*December 1990). Published as
Efficient Algorithms for Optical Computing with the discrete Fourier transform
(DFT) primitive, *Journal of Applied
Optics*, Vol. 36, 1997, pp. 7327-7340. [PDF]
or [PostScript]
[PDF]

87. John Canny, A. Rege, and John H. Reif, An Exact Algorithm for
Kinodynamic Planning in the Plane. *6th Annual
ACM Symposium on Computational Geometry*, Berkeley, CA, June 1990, pp.
271-280. [PDF]
Published in *Discrete and Computational
Geometry*, Vol. 6, 1991, pp. 461-484. [PDF]

88. John H. Reif
and Sandeep Sen, Randomized Algorithms for Binary Search and Load Balancing on
Fixed Connection Networks with Geometric Applications. *2nd Annual ACM Symposium on Parallel Algorithms and Architectures*,
Crete, Greece, July 1990, pp. 327-337. Published in *SIAM Journal of Computing* 23:3, June, 1994, pp.633-651. [PDF]

89. 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.

90. Hristo Djidjev and John H. Reif, An Efficient Algorithm for the
Genus Problem with Explicit Construction of Forbidden Subgraphs. *23rd Annual ACM Symposium on Theory of
Computing*, New Orleans, LA, May 1991, pp. 337-347. [PDF]

91. Hillel Gazit and John H. Reif, A Randomized Parallel Algorithm for
Planar Graph Isomorphism. *2nd Annual ACM
Symposium on Parallel Algorithms and Architectures*, Crete, Greece, July 1990,
pp. 210-219. Published in* Journal of
Algorithms, *Vol. 28, No. 2, pp. 290-314, August 1998. [PostScript]
[PDF]

92. Victor Y. Pan and John H. Reif, The Parallel Computation of
Minimum Cost Paths in Graphs by Stream Contraction, *Information Processing Letters*, Vol. 40, October 25,1991, pp.
79-83. [PDF]

93. John H. Reif and Steve R. Tate, Approximate Kinodynamic Planning
Using *L*2-norm Dynamic Bounds. Duke
University Technical Report CS-1990-13, 1989. Published in *Computers and Mathematics with Applications*, Vol. 27, No.5,
pp.29-44, March 1994. [PostScript]
[PDF]

94. Royals, M., Tassos Markas, N. Kanopoulos, John H. Reif and James
A. Storer, On the Design and Implementation of a Lossless Data Compression and
Decompression Chip, IEEE Journal of Solid State
Circuits (JSSC), Vol. 28, No. 9, pp. 948-953, Sep. 1993. [PDF]

95. Micheal Karr, S. Krishnan, John H. Reif, Derivation of the
Ellipsoid Algorithm, Duke University Technical Report CS-1991-17, (1990). [PDF]

96. John H. Reif and A. Tyagi, An Optical Delay Line Memory Model with
Efficient Algorithms. *Advanced Research
in VLSI Conference*, MIT Press, Santa Cruz, CA, March 1991. Published in *Optical Engineering*, 36(09), pp.
2521-2535, Sept. (1997). [PostScript]
[PDF]

97. Selman Azhar and John H. Reif, Crypto-Complexity Based Models of
Efficiency in Capital Markets, 1994. [PDF]

98. John H. Reif and Steve R. Tate, Continuous Alternation: The
Complexity of Pursuit in Continuous Domains, Special Issue on Computational
Robotics: the Geometric Theory of Manipulation, Planning and Control, *Algorithmica*, Vol. 10, pp. 151-181,
1993. [PostScript]
[PDF]

99. John H. Reif and Akitoshi Yoshida, Optical Expanders with
Applications in Optical Computing, *Journal
of Applied Optics*, 32, 1993, pp. 159-165. [PDF]
or [PostScript]
[PDF]

100. James A. Storer and John H. Reif, Low-Cost Prevention of Error
Propagation for Data Compression with Dynamic Dictionaries, *Proceedings: IEEE Data Compression
Conference (DCC'97)* Snowbird, UT, IEEE Computer Society Press, James A.
Storer, Martin Cohn (Eds.), March 1997, pp. 171-180. Published as Error
Resilient Optimal Data Compression, SIAM Journal of Computing (SICOMP), Vol 26,
Num 4, July 1997, pp. 934-939. [PostScript]
[PDF]

101. Peter H. Mills, Lars S. Nyland, J.F. Prins, John H. Reif and
Robert A. Wagner, Prototyping Parallel and Distributed Programs in *Proteus*. *3rd IEEE Symposium on Parallel and Distributed Processing*, Dallas,
TX, pp. 10-19, IEEE, 1991. [PostScript]
[PDF]

102. James A. Storer, Tassos Markas and John H. Reif, A Massively
Parallel VLSI Compression System using a Compact Dictionary. *IEEE Workshops on VLSI & Signal
Processing*, 1990, San Diego, CA. Published as A Massively Parallel VLSI
Design for Data Compression Using a Compact Dictionary, *VLSI Signal Processing*, No. 4, 1990 (edited by H.S. Moscovitz and
K. Yao and R. Jain), Chapter 32, IEEE Press, 1990, New York, NY, pp. 329-338. [PDF]

103. S. Krishnan and John H. Reif, Towards Randomized Strongly
Polynomial Algorithms for Linear Programming, Duke University Technical Report
CS-1991-18. [PDF]

104. Victor Y. Pan and John H. Reif, Decreasing the Precision of
Linear Algebra Computations by Using Compact Multigrid and Backward Interval
Analysis. *4th SIAM Conference in Applied
Linear Algebra*,* *Minneapolis, MN,
September 1991. Published as Compact Multigrid, *SIAM Journal of Scientific and Statistical Computing*, Vol. 13, No.
1, pp. 119-127, (1992). [PDF]

105. Tassos Markas and John H. Reif, Fast Computations of Vector
Quantization Algorithms. NASA Technical Report TR-91-58, 1991.

106. Tassos Markas and John H. Reif, Image Compression Methods with
Distortion Controlled Capabilities. *IEEE
Data Compression Conference (DCC 91)*, Snowbird, UT, IEEE Computer Society
Press, April 1991, pp. 93-102. Published as Quad Tree Structures for Image
Compression Applications, special issue of *Journal
of Information Processing and Management*, 1992, pp. 707-721. [PDF]

107. Joseph Cheriyan and John H. Reif, Algebraic Methods for Testing
the *k*-Vertex Connectivity of Directed
Graphs, *3rd Annual ACM-SIAM Symposium on
Discrete Algorithms*, Orlando, Florida,*
*1992, pp. 203-210. [PDF]
Published as Directed *s-t* Numberings,
Rubber Bands, and Testing Digraph *k*-Vertex
Connectivity, in *Combinatorica* 14(4)
pp. 435-451, 1994. [PDF]

108. John H. Reif and Akitoshi Yoshida, Optical Techniques for Image
Compression. *2nd Annual IEEE Data
Compression Conference (DCC 92)*, Snowbird, UT, IEEE Computer Society Press,
James A. Storer, Martin Cohn (Eds.), March 1992, pp. 32-41. Also in *Image and Text Compression*, edited by
James A. Storer, Kluwer Academic Publishers, 1992. Published as "Optical
Computing Techniques for Image/Video Compression," in *Proceedings of the IEEE*, 82:6, June 1994, pp. 948-954. [PDF]

109. John H. Reif and Hongyan Wang, On Line Navigation Through Regions
of Variable Densities. ARO Computational Geometry Workshop, Raleigh, North
Carolina, October, 1993. Rewritten as On-Line Navigation Through Weighted
Regions. [PostScript]
[PDF]

110. Ming Kao, John H. Reif, and Steve R. 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]

111. John H. Reif, O(log2 n) Time Efficient Parallel Factorization of
Dense, Sparse Separable, and Banded Matrices. *5th Annual ACM Symposium on Parallel Algorithms and Architectures
(SPAA'94)*, Cape May, NJ, June 1994, pp. 114-121.** **[PostScript]
[PDF]

112. John H. Reif, An *O*(*n* log^3 *n*) Algorithm for the Real Root Problem. *34th Annual IEEE Conference on Foundations of Computer Science (FOCS
'93) Proceedings*, November 1993, Palo Alto, CA, pp. 626-635. Revised as An
Efficient Algorithm for the Real Root and Symmetric Tridiagonal Eigenvalue
Problems, 1994. [PostScript]
[PDF]
and [PostscriptFigures]

113. Tassos Markas and John H. Reif, Memory-Shared Parallel
Architectures for Vector Quantization Algorithms, 1992. Picture Coding
Symposium, Lusanne Switzerland, March, 1993.

114. Peter H. Mills, Lars S. Nyland, Jan Prins, and John H. Reif,
Prototyping N-body Simulation in *Proteus*,
*Sixth International Parallel Processing
Symposium*, IEEE, Beverly Hills, CA, pp. 476-482, 1992. [PostScript]
[PDF]

115. Deganit Armon and John H. Reif, Space and time efficient implementations of parallel nested dissection, *4th Annual ACM Symposium on Parallel Algorithms and Architectures*, San Diego, CA, July 1992. Submitted
for journal publication as Space and Time Efficient Implementations of a
Parallel Direct Solver using Nested Dissection. [__PDF__]

116. Peter H. Mills, Lars S. Nyland, Jan Prins, and John H. Reif,
Prototyping High-Performance Parallel Computing Applications in *Proteus*. *DARPA Software Technology Conference*, May, 1992. [PostScript]
[PDF]

117. Victor Y. Pan, John H. Reif, Steve R. Tate. The Power of
Combining the Techniques of Algebraic and Numerical Computing: Improved Approximate Multipoint
Polynomial Evaluation and Improved Multipole Algorithms, 32th Annual IEEE
Symposium on Foundations of Computer Science (FOCS'92), Pittsburgh, PA, Oct.
1992, pp. 703-713. Rewritten as John H. Reif and Steve R. Tate, "N-body
simulation I: Fast algorithms for potential field evaluation and Trummer's
problem". Tech. Report. #N-96-002, Univ. of North Texas, Dept. of Computer
Science (1996). [PostScript]
[PDF] Submitted for journal
publication as as John H. Reif and Steve R. Tate, Efficient
N-body Simulation: Fast Algorithms for Potential Field Evaluation and Trummer’s
Problem [PDF].

118. William L. Hightower, Jan 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]

119. Yijie Han, Victor Y. Pan, and John H. Reif, Efficient Parallel
Algorithms for Computing All Pair Shortest Paths in Directed Graphs. University
of Kentucky Technical Report 204-92. *4th
Annual ACM Symposium on Parallel Algorithms and Architectures*, San Diego,
CA, July 1992, pp. 353-362. Published in Algorithmica, Vol 17, pp. 399-415,
1997. [PDF]

120. John H. Reif and Hongyan Wang, Social Potential Fields: A
Distributed Behavioral Control for Autonomous Robots, *Workshop on Algorithmic Foundations of Robotics (WAFR'94)*, San
Francisco, California, February, 1994; The Algorithmic Foundations of Robotics,
A.K.Peters, Boston, MA. 1995, pp. 431-459. Published in Robotics and Autonomous
Systems, Vol. 27, no.3, pp.171-194, (May 1999). [PostScript]
[PDF]

121. John H. Reif and Steve R. Tate, Dynamic Algebraic Algorithms, *Proceedings of the* *5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'94),* TX,
Jan. 1994. pp.290-301. Published as On Dynamic Algorithms for Algebraic
Problems, Journal of Algorithms, Volume 22, Number 2, pp. 347-371, February
1997. [PostScript]
[PDF]

122. John H. Reif and Steve R. Tate, Dynamic Parallel Tree
Contraction, *5th Annual ACM Symposium on
Parallel Algorithms and Architectures (SPAA'94)*, Cape May, NJ, June 1994.
pp.114-121. Revised version submitted for journal publication. [PDF]

123. Deganit Armon and John H. Reif, A Dynamic Separator Algorithm
with Applications to Computational Geometry and Nested Dissection, *3rd Annual Workshop on Algorithms and Data
Structures (WADS '93)*, Montreal, Quebec, Canada, August, 1993, pp. 107-118.
[PDF]

124. Selman Azhar, Greg J. Badros, Arman Glodjo, Ming Kao, and John H.
Reif, Data Compression Techniques for Stock Market Prediction, *Proceedings: IEEE Data Compression
Conference (DCC'94)*, Snowbird, UT, IEEE Computer Society Press, James A.
Storer, Martin Cohn (Eds.), March 1994, pp. 72-82. [PDF]

125. Joseph Cheriyan and John H. Reif, Parallel and Output Sensitive
Algorithms for Combinatorial and Linear Algebra Problems, 1992. *4th Annual ACM Symposium on Parallel
Algorithms and Architectures (SPAA'93*), Velon, Germany, July 1993, p.50-56.
Published as John H. Reif, Parallel Output Sensitive Algorithms for Combinatorial
and Linear Algebra Problems, *Journal of
Computer and System Sciences*, Vol. 62, May 2001, pp. 398-412. [PostScript] [PDF]

126. Sotiris E. Nikoletseas, John H. Reif, Paul G. Spirakis, Moti
Yung, Stochastic Graphs Have Short Memory: Fully Dynamic Connectivity in
Poly-Log Expected Time. *Proceedings of
the 22nd Annual Colloquium on Automata, Languages and Programming (ICALP'95)*,
Szeged, Hungary, July 1995, pp. 159-170. [PDF]

127. Steve R. Tate and John H. Reif, The Complexity of N-body
Simulation, *Proceedings of the 20th
Annual Colloquium on Automata, Languages and Programming (ICALP'93)*, Lund,
Sweden, July, 1993, pp. 162-176. [PostScript]
[PDF]

128. Tassos Markas and John H. Reif, Multispectral Image Compression
Algorithms, *Proceedings: IEEE Data
Compression Conference* *(DCC'93)*,
Snowbird, UT, IEEE Computer Society Press, James A. Storer, Martin Cohn (Eds.),
pp. 391-400, March 1993. [PDF]

129. Peter H. Mills, Jan Prins, and John H. Reif, Rate Control as a
Language Construct for Parallel and Distributed Programming, Proc. IEEE
Workshop on Parallel and Distributed Real-Time Systems (IPPS'93), pp. 164-170,
1993. [PostScript]
[PDF]

130. Richard Barakat and John H. Reif, Diffraction Realization of an
Optical Expander, (1993). [PDF]

131. Lars S. Nyland, Jan F. Prins, and John H. Reif, A Data Parallel
Implementation of the Adaptive Fast Multipole Algorithm. *Dartmouth Institute for Advanced Graduate Studies (DAGS '93),*
Hanover, NH, June, 1993, pp. 111-123. [PostScript]
[PDF]

132. 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]

133. Andrew Neff and John H. Reif, An *O*(*n^{*1+epsilon} log *b*) Algorithm for the Complex Roots
Problem. *35th Annual IEEE Conference on
Foundations of Computer Science (FOCS '94) Proceedings*, Santa Fe, NM,
November 1994. pp. 540-547. Improved Paper Published as An Efficient Algorithm
for the Complex Roots Problem, Journal of Complexity, 12(2) pp. 81-115, (June
1996). [PostScript]
[PDF]

134. Andrew Goldberg, Jan Prins, Rickard Faith, Zhiyong
Li, Peter H. Mills, Lars S. Nyland, Daniel Palmer, John H. Reif, James Riely,
and Stephen Westfold, The Proteus System for the Development of Parallel
Applications. Prototyping and Software Development (Malcolm C. Harrison, ed.),
Chapter 6, pp. 151-190, Digital Book, 1996. [PostScript] [PDF]

135. Peter H. Mills, Lars S. Nyland, J.F. Prins, and John H. Reif,
Software Issues in High-Performance Computing and a Framework for the
Development of HPC Applications. In *Developing
a Computer Science Agenda for High Performance Computing* (U. Vishkin, ed.)
pp. 110-117, ACM, 1994. [PostScript]
[PDF]

136. Andrew Goldberg, Peter H. Mills, Lars S. Nyland, Jan F. Prins,
John H. Reif, and J. Riely, Specification and Development of Parallel
Algorithms with the Proteus System, Specification of Parallel Algorithms, *DIMACS Series in Discrete Mathematics and
Theoretical Computer Science*, AMS Press, Vol. 18, 1994, pp. 383-399. [PostScript]
[PDF]

137. Victor Y. Pan and John H. Reif, Generalized Compact Multi-grid, *Computers Math Applications, Volume *25,
Number 9, pp. 3-5, May 1993. [PDF]

- John H. Reif and James A. Storer,
3-Dimensional Shortest Paths in the Presence of Polygonal Obstacles. 13th
*Symposium on Mathematical Foundations of Computer Science*,*(Edited by*Michal Chytil, Ladislav Janiga, Václav Koubek) Czechoslovakia, August 29-September 2, 1988, pp. 85-92. Published as A Single-Exponential Upper Bound for Finding Shortest Paths in Three Dimensions.*Journal of the ACM(JACM*), Vol. 41, No. 5, Sept. 1994, pp. 1013-1019. [PDF]

139. Sefeng 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]

140. John H. Reif, Efficient Parallel Solution of Sparse Eigenvalue
and Eigenvector Problems, *Proceedings of
the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS'95)*
Milwaukee, WI, October 23-25, 1995, pp. 123-132. Published as Efficient
Parallel Computation of the Characteristic Polynomial of a Sparse, Separable
Matrix, Algorithmica, 29: 487-510 (2001). [PDF]

141. Akitoshi Yoshida, Jannick P. Rolland and
John H. Reif, Design and Applications of a High Resolution Insert Head-Mounted
Display. *IEEE Virtual Reality Annual
International Symposium (VRAIS'95)*, Research Triangle Park, NC, March
11-15, 1995, pp. 84-93. [PostScript] [PDF] Also, Jannick
P. Rolland and Akitoshi
Yoshida, and John H. Reif, Optical design and analysis of a head-mounted
display with a high-resolution insert, (Novel Optical Systems Design and
Optimization, Jose M. Sasian; Ed.,), Proc. SPIE Vol. 2537, pp. 71-82, Aug.
1995. Published as Jannick
P. Rolland, Akitoshi
Yoshida, Larry D. Davis, and John H. Reif, High
resolution inset head-mounted display, Applied Optics: Optical Technology and
Biomedical Optics, 37(19), 4183-4193 (1998). [PDF]

142. Sandeep K. S. Gupta, Zhiyong Li, and John H. R