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]