Books

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]