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. Handbook of Randomized Computing
(Edited by S. Rajasekaran, pp. M. Pardalos, John H. Reif and J. Rolim), 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), Montral,
Qubec, 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. Sudheer Sahu and John H. Reif, DNA-based
Self-assembly and Nanorobotics, Published by VDM Verlag Dr. Mueller e.K.,
Saarbrcken, Germany, 128 pages, (November 10, 2008) ISBN-10: 363909770X, ISBN-13:
978-3639097702.
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.
R. 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 H.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 S. 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.
I. Filotti, G. 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.
G.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 G.L. Peterson, John
H. Reif, and S. 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.
G.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 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 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.
J.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 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.
G.L. Peterson
and John H. Reif, Decision Algorithms for Multiplayer Games of Incomplete
Information. Harvard University, TR-34-81. Published as G.L. Peterson, John H.
Reif, and S. 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 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 Spirakis, Strong k-connectivity in Digraphs and
Random Digraphs, Harvard University TR-25-81. [PDF])
22.
John H. Reif
and Paul 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 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 pp. 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 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.
L.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 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.
G. Kar, C.N.
Nikolaou, 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.
M. Ben-Or, D.
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.
R. Nair, A.
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
Publishers, pp. 327-338. [PDF]
39.
John H. Reif
and J.D. 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.
P. 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.
V. 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.
G. 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.
S. 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 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. [PDF]
46.
V. 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,
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]
48.
John H. Reif
and S. Smolka, The Complexity of Reachability in Distributed Communicating
Processes, Journal of Acta Informatica, Vol. 25(3), April 1988, pp.333-354. [PDF]
49.
S. 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.
J.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.
V. 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 J.A. Storer, Shortest Paths in Euclidean Space with Polyhedral Obstacles. Symposium on Mathematical Foundations of
Computer Science, Czechoslovakia,
August 1988, pp. 85-92. Published as 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 J.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.
R.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.
V. 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.
J. 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.
R. 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.
R. 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 as Adaptive and Learning
Systems: Theory and Applications, K.S.
Narendra, ed., Plenum Press, New York, NY, 1986. [PDF]
61.
P. 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.
C.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, S. Kasif, and D. 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 S. 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.
J. Canny, B.
Donald, John H. Reif and pp. 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.
S. 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 S. 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.
V.
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 in Journal of
Computer and System Sciences, 49:3,
December, 1994, pp. 517-561. [PostScript] [PDF]
70.
S. 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.
V. 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.
J.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.
E.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 as D.W. Blevin, E.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 S. 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.
L.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.
D.W. Blevins,
E.W. Davis, R.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 S. 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 S. 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. [PostScript] [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,
D. Tygar, and A. 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.
S. Azhar, A.
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, 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]
84.
John H. Reif
and S. 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 S. Rajasekaran John H. Reif S. 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.
V. 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.
J. 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 S. 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.
H. 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.
H. 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.
V. 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 S. Tate, Approximate Kinodynamic Planning Using L2-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., T.
Markas, N. Kanopoulos, John H. Reif and J. 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.
M. 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.
S. Azhar and
John H. Reif, Crypto-Complexity Based Models of Efficiency in Capital Markets,
1994. [PDF]
98.
John H. Reif
and S. 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 A. Yoshida, Optical Expanders with Applications in Optical Computing, Journal of Applied Optics, 32, 1993, pp.
159-165. [PDF]
or [PostScript]
[PDF]
100.
J. 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.
P.H. Mills,
L.S. Nyland, J.F. Prins, John H. Reif and R.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.
J.A. Storer,
T. 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. Krishan and
John H. Reif, Towards Randomized Strongly Polynomial Algorithms for Linear
Programming, Duke University Technical Report CS-1991-18. [PDF]
104.
V. 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.
T. 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.
J. 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 A. 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 J. 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 H. 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.
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]
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.
T. Markas and
John H. Reif, Memory-Shared Parallel Architectures for Vector Quantization
Algorithms, 1992. Picture Coding Symposium, Lusanne Switzerland, March, 1993.
114.
P. Mills, L.
Nyland, J. 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.
D. Armon and
John H. Reif, An Optimal Space and Efficient Parallel Nested Dissection
Algorithm, 1992. 4th Annual ACM Symposium
on Parallel Algorithms and Architectures, San Diego, CA, July 1992. [PDF]
116.
P. Mills, L.
Nyland, J. Prins, and John H. Reif, Prototyping High-Performance Parallel
Computing Applications in Proteus. DARPA Software Technology Conference,
May, 1992. [PostScript]
[PDF]
117.
V. Pan, John
H. Reif, S. 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 S. 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]
118.
W.L.
Hightower, J. 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.
Y. Han, V.
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 H. 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 S. 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 S. 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. [PostScript] [PDF]
123.
D. 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.
S. Azhar, G.
Badros, A. Glodjo, M. 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.
J. 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.
S.
Nikoletseas, John H. Reif, P.G. Spirakis, and M. 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.
S.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.
P. Mills, J.
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.
R. Barakat and
John H. Reif, Diffraction Realization of an Optical Expander, (1993). [PDF]
131.
L. S. Nyland,
J. 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.
S. 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.
A. 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.
A. Goldberg,
J. Prins, R. Faith, Z. Li, pp. Mills, L. Nyland, D. Palmer, John H. Reif, J.
Riely, and S. Westfold, The Proteus System for the Development of Parallel
Applications. Prototyping and Software
Development (M.C. Harrison, ed.), Lecture Notes in Computer Science, pp.
151-190, Springer-Verlag, 1996. [PostScript]
[PDF]
135.
P.H. Mills,
L.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.
A. Goldberg,
pp. H. Mills, L. S. Nyland, J. F. Prins, John H. Reif, and J. Riely,
Specification and Development of Parallel Algorithms with the Proteus System, DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, AMS Press, Vol. 18, 1994, pp. 383-399. [PostScript] [PDF]
137.
V. Pan and
John H. Reif, Generalized Compact Multi-grid, Computers Math Applications, Volume 25, Number 9, pp. 3-5, May
1993. [PDF]
138.
John H. Reif
and J. Storer, 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.
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]
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.
A. Yoshida, J.
Rolland and John H. Reif, and, 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, J.
Rolland and A. 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 Rolland, J.P., A. Yoshida, L. 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.
S. Gupta, Z.
Li, and John H. Reif, Generating Efficient Programs for Two-Level Memories from
Tensor-Products. Proceedings of the 7th
IASTED/ISMM International Conference on Parallel and Distributed Computing and
Systems Washington DC, October 1995, pp. 510-513. [PostScript] [PDF]
143.
John H. Reif,
Parallel Biomolecular Computation: Models and Simulations. Proceedings: 7th Annual ACM Symposium on Parallel Algorithms and
Architectures (SPAA'95) Santa Barbara, CA, July 1995, pp. 213-223.
Published in Algorithmica, special issue on Computational Biology, Vol. 25, No.
2, 142-176, 1999. [PDF]
[PostScript] and
[PostScriptFigures]
144.
John H. Reif,
Work Efficient Parallel Solution of Toeplitz Systems and Polynomial GCD. Proc. of the 27th ACM Symposium on Theory of
Computing (STOC 95), Las Vegas, NV, May 29-June 1, 1995, pp. 751-761.
Revised as Efficient Parallel Factorization and Solution of Structured and
Unstructured Linear Systems, Journal of
Computer and System Sciences, Vol.
71, Issue 1 (July 2005), pp. 86 - 143. [PDF]
[PDF]
145.
S. Gupta, Z.
Li, and John H. Reif, Synthesizing Efficient Out-of-Core Programs for Block
Recursive Algorithms using Block-Cyclic Data Distributions. Proceedings of the 1996 International
Conference on Parallel Processing, Bloomingdale, IL, Vol. II, pp. 142-149,
(August 1996). Published in IEEE
Transactions on Parallel and Distributed Systems, Vol. 10, No. 3, March
1999, pp. 297-315. [PDF] or [PDF]
146.
L. Nyland, J.
Prins, A. Goldberg, pp. Mills, John H. Reif, and R. Wagner. A Refinement
Methodology for Developing Data-Parallel Applications, Euro-Par'96, Lecture
Notes in Computer Science, Springer-Verlag, pp.145-150, 1996. [PDF]
147.
S. Chen and
John H. Reif, Compression of Trees and Digraphs, Abstract, Proceedings: IEEE Data Compression Conference (DCC'96), Snowbird,
UT, James A. Storer, Martin Cohn (Eds.), IEEE Computer Society Press, March
1996. [PDF]
148.
John H. Reif
and H. Wang, Nonuniform Discretization for
Kinodynamic motion planning and its applications, Workshop on Foundations of Robotics, Toulouse, France, July 1996,
pp. 97-112. Published in SIAM Journal of Computing (SICOMP), Volume 30, No. 1,
pp. 161-190, (2000). [PostScript]
[PDF]
149.
Z. Li, pp. H.
Mills, and John H. Reif, Models and Resource Metrics for Parallel and
Distributed Computation, Proc. 28th
Annual Hawaii International Conference on System Sciences (HICSS-28
Parallel Algorithms Software Technology Track), Wailea, Maui, Hawaii, pp.
133-143, January 3-6, 1995. Published in Parallel
Algorithms and Applications, Vol. 8, pp. 35-59, 1996. [PostScript]
[PDF]
150.
E. Gelenbe,
N.Schmajuk, J. Staddon, and John H. Reif, Autonomous Search and the Search for
Robots and Mines: A Survey, Robotics and Autonomous Systems, Vol. 22, pp.
23-33. (November 1997). [PostScript]
[PDF]
151.
John H. Reif,
Approximate Complex Polynomial Evaluation in Near Constant Work Per Point.
Proc. 29th ACM Symposium on Theory of Computing (STOC97), El Paso, Texas, pp.
30-39 (May 4-6, 1997). Published in SIAM
Journal of Computing (SICOMP), Vol. 28, Number 6,
pp. 2059-2089, 1999. [PostScript] [PDF]
152.
John H. Reif,
Efficient Approximate Solution of Sparse Linear Systems, Published in Computers and Mathematics with Applications,
Vol. 36, No. 9, Nov. 1998, pp. 37-58. [PostScript] [PDF] (Also, see
errata, Computers and Mathematics with Applications, Vol. 38, No. 9, 1999, pp.
141-141. [PDF])
153.
John H. Reif
and S. Tate, Fast spatial decomposition and closest pair computation for
limited precision input, Journal of Algorithmica, Volume 28, Number 3, pp.
271-287 (2000). [PDF] or [PostScript] [PDF]
154.
S. Chen and
John H. Reif, Fast and Compact Fast and Compact Volume Rendering in the
Compressed Transform, Proceedings: IEEE
Data Compression Conference (DCC'97) Snowbird, UT, James A. Storer, Martin
Cohn (Eds.), IEEE Computer Society Press, March 1997, pp. 271-280. [PDF]
155.
John H. Reif
and D. Yen, Derivation of Parallel Graph Connectivity Algorithms via Stream
Contraction, Duke University Technical Report, 1989. [PDF]
156.
John H. Reif,
Local Parallel Biomolecular Computation, Proc. DNA-Based Computers, III:
University of Pennsylvania, June 23-26, 1997. [PDF]
DIMACS Series in Discrete Mathematics and Theoretical Computer Science, H.
Rubin and D. H. Wood, editors. American Mathematical Society, Providence, RI,
vol. 48, 1999, pp. 217-254. [PDF];
Figures: [PDF]
157.
John H. Reif,
On the Impossibility of Interaction-Free Quantum Sensing for Small I/O
Bandwidth, Information and Computation,
Jan 2000, pp. 1-20. [PostScript] [PDF]
158.
John H. Reif,
Robust, Adaptive and Dynamic Robotic Motion Planning, 19th NSF Design and
Manufacturing Grantees Conference, Monterrey, Mexico, Jan 1998. [PostScript] [PDF]
159.
John H. Reif
and S. Sen, Parallel Computational Geometry: An approach using randomization.
Published as Chapter 8 in Handbook of
Computational Geometry, Edited by Jorge Urrutia and Jrg-Rudiger Sack,
Elsevier Science Publishing, Amsterdam, the Netherlands, pp. 765-828. 1999. [PDF] or [PDF]
160.
John H. Reif,
Paradigms for Biomolecular Computation, First
International Conference on Unconventional Models of Computation, Auckland,
New Zealand, January 5-9, 1998. Published in
Unconventional Models of Computation, (edited by C.S. Calude, J. Casti, and
M.J. Dinneen), DMTCS Series, Springer-Verlag, Singapore, January 1998, pp.
72-93. [PostScript]
[PDF]
161.
John H. Reif
and J. A. Storer, Optimal Lossless Compression of a Class of Dynamic Sources,
Data Compression Conference (DCC'98), Snowbird, UT, James A. Storer, Martin
Cohn (Eds.), IEEE Computer Society Press, pp. 501-510, March, 1998. Published
as Optimal Encoding of Non-stationary Sources, Special Issue of Information
Sciences, Volume 135, pp. 87-105 (2001). [PDF]
162.
John H. Reif
and H. Wang, The Complexity of the Two Dimensional Curvature-Constrained
Shortest-Path Problem, Third
International Workshop on Algorithmic Foundations of Robotics (WAFR98), Pub. by A. K. Peters Ltd,
Houston, Texas, pp. 49-57, June, 1998. [PostScript]
[PDF]
163.
John H. Reif
and Z. Sun, The Computational Power of Frictional Mechanical Systems, Third International Workshop on Algorithmic
Foundations of Robotics, (WAFR98),
Pub. by A. K. Peters Ltd, Houston, Texas, pp. 223-236, Mar. 5-7 1998. Published
as On Frictional Mechanical Systems and Their
Computational Power, SIAM Journal of Computing (SICOMP), Vol. 32, No. 6,
pp. 1449-1474, (2003). [PDF]
or [PDF].
Talk: [HTML]
164.
A. Gehani and
John H. Reif, Micro Flow Bio-Molecular Computation, 4th DIMACS Workshop on DNA
Based Computers, University of Pennsylvania, June 15-19, 1998. DNA Based Computers, IV, DIMACS Series in
Discrete Mathematics and Theoretical Computer Science, (ed. H. Rubin),
American Mathematical Society, 1999. Also in a special issue of Biosystems,
Journal of Biological and Informational Processing Sciences, Vol. 52, Nos. 1-3,
(Edited By L. Kari, H. Rubin, and D. H. Wood), pp. 197-216, (October 1999). [PostScript]
[PDF]
or [PDF]
Talk: [PDF]
165.
John H. Reif,
Alternative Computational Models: A Comparison of Biomolecular and Quantum
Computation, Invited paper, 18th International
Conference on Foundations of Software Technology and Theoretical Computer
Science (FSTTCS1998), Chennai, India (December, 17-19, 1998). [PDF]
166.
John H. Reif
and Zheng Sun, Nano-Robotics Motion Planning and Its Applications in
Nanotechnology and Biomolecular Computing, NSF
Design and Manufacturing Grantees Conference, Jan 5-8, 1999. [HTML]
167.
T. H. LaBean,
H. Yan, J. Kopatsch, F. Liu, E. Winfree, John H. Reif and N.C. Seeman, The
construction, analysis, ligation and self-assembly of DNA triple crossover
complexes, Journal of American Chemistry
Society(JACS) 122, pp. 1848-1860 (2000). [PDF]
168.
John H. Reif
and Sukhendu Chakraborty, Efficient and Exact Quantum Compression, Journal of
Information and Computation, Vol. 205, pp. 967-981 (2007). [PDF]
[PDF]
169.
John H. Reif,
Quantum Computing. In book ŌBio-inspired and
Nanoscale Integrated ComputingĶ, Chapter 3, pp. 67-110 (edited by
Mary Mehrnoosh Eshaghian-Wilner), Publisher: Wiley, Hoboken, NJ, USA,
(February
2009). [PDF]
170.
John Fischer
and John H. Reif, Nonparametric Multiscale Multimodal Model for
Detection/Recognition, Multi-Modality Image Fusion Conference, Rochester, NY,
Oct 6-7, 1999. [PDF]
171.
A. Gehani, T.
H. LaBean, and John H. Reif, DNA-based Cryptography, Proc. DNA Based Computers
V: Cambridge, MA, June 14-16, 1999. Published in DIMACS Series in Discrete
Mathematics and Theoretical Computer Science, Volume 54, edited by E. Winfree
and D.K. Gifford, American Mathematical Society, Providence, RI, pp. 233-249,
(2000). [PDF]
Talk: [PDF].
Published as an invited chapter in "Aspects of
Molecular Computing - Essays dedicated to Tom Head on the occasion of his 70th
Birthday", Springer Verlag series in Natural Computing (edited by N. Jonoska, G.
Paun and G. Rozenberg) LNCS 2950 Festschrift, Springer, pp. 167-188, (2004). [PDF]
172.
T. H. LaBean,
E. Winfree, and John H. Reif, Experimental Progress in Computation by
Self-Assembly of DNA Tilings, Proceeding of DNA Based Computers V: Cambridge,
MA, June 14-16, 1999. Published in DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, Volume 54, edited by E. Winfree and D.K. Gifford,
American Mathematical Society, Providence, RI, pp. 123-140, (2000). [PostScript]
[PDF] Talk: [HTML
Lecture]
173.
John H. Reif
and Z. Sun. An efficient approximation algorithm for weighted region shortest
path problem. In Proceedings of the 4th
Workshop on Algorithmic Foundations of Robotics (WAFR2000), A. K. Peters Ltd Publishers,
Hanover, New Hampshire, pp. 191-203, Mar. 16-18 2000. [PDF]
[PostScript].
Published as Z. Sun and John H. Reif, On Finding Approximate Optimal Paths in Weighted Regions,
Journal of Algorithms, Volume 58, Number 1, pp. 1-32, January 2006. [PDF]
174.
John H. Reif
and Z. Sun. Movement planning in the presence of flows. In Proceedings of the 7th International Workshop on
Algorithms and Data Structures (WADS2001), volume 2125 of Lecture Notes in Computer Science, pp.
450-461, Brown University, Providence, RI, August 8-10, (2001). Published in
Algorithmica, Volume 39, Number 2, pp. 127-153, February 2004. [PDF] or [PDF]. Talk: [PDF]
175.
John H. Reif
and T. H. LaBean, Computationally Inspired Biotechnologies: Improved DNA
Synthesis and Associative Search Using Error-Correcting Codes and
Vector-Quantization, Sixth International Meeting on DNA Based Computers (DNA6), Leiden, The Netherlands (June 2000). DIMACS
Series in Discrete Mathematics and Theoretical Computer Science, Edited by A.
Condon and G. Rozenberg. Lecture Notes in Computer Science, Springer-Verlag,
Berlin Heidelberg, vol. 2054, pp. 145-172
(2001) [PostScript]
[PDF]
Talk: [PDF]
176.
John H. Reif,
T.H. LaBean, and N.C. Seeman, Challenges and Applications for Self-Assembled
DNA Nanostructures, Proc. Sixth International Workshop on DNA-Based Computers,
Leiden, The Netherlands, June 13-17, 2000. Published in DIMACS Series in
Discrete Mathematics and Theoretical Computer Science, Edited by A. Condon and
G. Rozenberg. Lecture Notes in Computer Science, Springer-Verlag, Berlin
Heidelberg, vol. 2054, 2001, pp. 173-198. [PostScript]
[PDF]
Talk: [PDF]
[PPT]
177.
C. Mao, T.H. LaBean, John H. Reif, N. C. Seeman,
Logical Computation Using Algorithmic Self-Assembly of DNA Triple-Crossover
Molecules, Nature, vol. 407, Sept. 28 2000, pp. 493-495; C. Erratum: Nature
408, 750-750(2000). [PDF]
or [PDF]
178.
John H. Reif
and T. H. LaBean, and N.C. Seeman. Programmable Assembly at the Molecular
Scale: Self-Assembly of DNA Lattices, Invited paper, 2001 IEEE International
Conference on Robotics and Automation (ICRA2001), Seoul, Korea, ed. Lee Beom, pp. 966-971 (May, 2001). [PDF]
179.
Z. Sun and
John H. Reif. BUSHWHACK: An approximation algorithm for minimal paths through
pseudo-Euclidean spaces. In Proceedings
of the 12th Annual International Symposium on Algorithms and Computation(ISAAC01), Christchurch, New Zealand, Dec 19-21,
2001, Volume 2223 of Lecture Notes in
Computer Science, pp. 160-171, Dec, 2001. Published in IEEE Transactions on Systems, Man, and
Cybernetics (SMC), Part B: Cybernetics, Vol. 37, No. 4, pp. 925-936 (2007). [PDF]
[PDF]
180.
John H. Reif,
T. H. LaBean, M. Pirrung, V. Rana, B. Guo, K. Kingsford, and G. Wickham,
Experimental Construction of Very Large Scale DNA Databases with Associative
Search Capability, Seventh International Meeting on DNA Based Computers (DNA7), Tampa, FL, June 11-13, 2001. Lecture Notes in Computer Science, Springer-Verlag, New
York, Volume 2340, pp. 231-247, (2002). [PostScript] [PDF] Talk: [PDF] [PPT]. Also published as John H. Reif,
Michael Hauser, Michael Pirrung, and Thomas LaBean, Application
of Biomolecular Computing to Medical Science: A Biomedical Database System for
Storage and Retrieval of Genetic Information and Material, Chapter 3 of
Complex Systems Science in Biomedicine (Edited by Thomas S. Deisboeck and J.
Yasha Kresh), International Topics in Biomedical Engineering Series, Springer
Publishers, New York, Chapter 3, pp. 701-735,
(2005). ISBN: 0-387-30241-7. [PDF] or [PDF]. Talk: [PDF][PPT]
181.
John H. Reif, DNA Lattices: A Method for Molecular Scale Patterning and
Computation, special issue on Bio-Computation, Computer and Scientific
Engineering Magazine, IEEE Computer Society, Vol. 4, No. 1, February 2002, pp.
32-41. [PostScript][PDF]
182.
John H. Reif,
The Emerging Discipline of Biomolecular Computation in the US, invited paper to the special issue on Biomolecular
Computing, New Generation Computing, edited by Masami Hagiya, Masayuki
Yamamura, and Tom Head, Vol. 20, No. 3, pp. 217-236, (2002). [PostScript][PDF] or [PDF]
183.
John H. Reif,
Molecular Assembly and Computation: From Theory to Experimental Demonstrations,
plenary paper, Twenty Ninth International Colloquium on Automata, Languages,
and Programming(ICALP), Mlaga, Spain (July 8, 2002). Lecture Notes in Computer
Science, New York, Volume 2380, pp. 1-21, (2002). [PostScript][PDF]
Talk: [PDF] [PPT]
184.
John
H. Reif, The Design of Autonomous DNA Nanomechanical Devices: Walking and
Rolling DNA. DNA Based Computers (DNA8), Sapporo, Japan, June 10-13, 2002,
(Edited by Masami Hagiya and Azuma Ohuchi), Lecture Notes in Computer Science,
No. 2568, Springer-Verlag, New York, (2003), pp. 22-37. Published in Natural
Computing, DNA8 special issue, Vol. 2, p 439-461, (2003). [PDF] or [PostScript][PDF] Talk: [PDF]
185.
Dage Liu, John
H. Reif, Thomas H. LaBean, DNA Nanotubes, Construction and Characterization of
Filaments Composed of TX-tile Lattice. DNA Based Computers (DNA8), Sapporo, Japan, June 10-13, 2002,
(Edited by Masami Hagiya and Azuma Ohuchi), Lecture Notes in Computer Science,
No. 2568, Springer-Verlag, New York, (2003), pp. 10-21. Published as DNA
nanotubes self-assembled from triple-crossover tiles as templates for
conductive nanowires, Proceedings of the National
Academy of Science(PNAS), Vol. 101, No. 3, pp. 717-722, (January 20,
2004). PubMed PMID: 14709674. [PDF]
186.
John
H. Reif, DNA Computation - Perspectives: Successes and Challenges, Science,
296: 478-479, April 19, 2002. PubMed
PMID: 11964464. [PostScript][PDF]
187.
Z.
Sun and John H. Reif, On Finding Energy-minimizing Paths on Terrains for a
Mobile Robot, 2003 IEEE International Conference on Robotics and Automation(ICRA2003),
Taipei, Taiwan, pp. 3782-3788, May
12-17, 2003. Published in IEEE Transaction on
Robotics, Volume: 21, Issue: 1, February 2005, pp. 102-114. [PDF]
188.
D.
Hsu, T. Jiang, John H. Reif, and Z. Sun, The Bridge Test for Sampling Narrow
Passages with Probabilistic Roadmap Planners, 2003 IEEE International
Conference on Robotics and Automation(ICRA2003), Taipei, Taiwan, Vol.3, pp.
4420 – 4426, Sept. 14-19, 2003. Published
as Z. Sun, D. Hsu, T. Jiang, H. Kurniawati, and J.H.Reif, Narrow Passage
Sampling for Probabilistic Roadmap Planning, IEEE Transactions on Robotics,
Volume 21, No. 6, Dec. 2005. pp. 1105–1115. [PDF]
189.
John
H. Reif and Zheng Sun, On Boundaries of Highly Visible Spaces and Applications,
14th Symposium on Fundamentals of
Computation Theory, Malm Hgskola, Sweden, August 12-15, 2003, Springer-Verlag
Lecture Notes in Computer Science, 2003. Invited paper published in Theoretical
Computer Science, Volume 354, Issue 3, (4 April 2006), pp. 379-390. [PDF] [PDF]
190.
Hao Yan,
Thomas H. LaBean, Liping Feng, and John H. Reif, Directed Nucleation Assembly
of Barcode Patterned DNA Lattices, Proceedings of the
National Academy of Science(PNAS), Volume 100, No. 14, pp. 8103-8108,
July 8, (2003). PubMed PMID: 12821776. [PostScript] [PDF]
191.
Hao Yan,
Liping Feng, Thomas H. LaBean, and John H. Reif, DNA Nanotubes, Parallel Molecular
Computation of Pair-Wise XOR Using DNA String Tile, Ninth International Meeting on DNA Based Computers
(DNA9), Madison, Wisconsin, June 2-4, 2003, (Edited by Junghuei
Chen and John H. Reif), Abstract in Lecture Notes in Computer Science,
Springer-Verlag, New York, (2003). Published as Parallel
Molecular Computations of Pairwise Exclusive-Or (XOR) Using DNA "String
Tile" Self-Assembly in Journal of American Chemistry Society(JACS), Vol. 125, No. 47, pp. 14246-14247, 2003. PubMed
PMID: 14624551. [PDF] or [PDF]; Supporting Information: [PDF]
192.
Hao Yan, Sung
Ha Park, Liping Feng, John H. Reif, and Thomas H. LaBean, 4x4 DNA Tile and Lattices: Characterization,
Self-Assembly and Metallization of a Novel DNA Nanostructure Motif, Ninth International Meeting on DNA Based Computers
(DNA9), Madison, Wisconsin, June 2-4, 2003, (Edited by Junghuei
Chen and John H. Reif), Lecture Notes in Computer Science,
Springer-Verlag, New York, (2003). Published as Hao Yan, Sung Ha Park, Gleb Finkelstein,
John H. Reif, and Thomas H. LaBean, DNA-Templated Self-Assembly of Protein
Arrays and Highly Conductive Nanowires, Science, Vol. 301, pp. 1882-1884, Sep
26 2003. PubMed PMID: 14512621. [PDF] Supporting Materials: [PDF] Supplemental Information: [PDF]
193.
Liping Feng,
Sung Ha Park, John H. Reif, and Hao Yan, A Two-State DNA Lattice Switched by
DNA Nanoactuator, Angewandte Chemie [International
Edition], Vol. 42, pp. 4342-4346, Sept. 2003. PubMed PMID: 14502706. [PDF] Supplemental Information: [PDF]
194.
Zheng Sun and John H.
Reif, Adaptive and Compact Discretization for Weighted Region Optimal Path
Finding. 14th Symposium on Fundamentals of Computation Theory, Malm Hgskola,
Sweden, August 12-15, 2003, Springer-Verlag Lecture Notes in Computer Science,
Vol. 2751, pp. 258-270, 2003. [PostScript] [PDF] or [PostScript] [PDF].
195.
Tinging
Jiang and John H. Reif, Efficient Methods for Stochastic Simulations of
Biomolecular Motions, submitted for publication, July, 2003. [PDF]
196.
H. Li, S.H.
Park, John H. Reif, T.H. LaBean, H. Yan, DNA-Templated Self-Assembly of Protein
and Nanoparticle Linear Arrays, Journal of American Chemistry Society (JACS), Vol. 126, No. 2, pp. 418-419, 2004. PubMed PMID:
14719910. [PDF]. Supporting Information: [PDF]
197.
Hao Yan, Peng
Yin, Sung Ha Park, Hanying Li, Liping Feng, Xiaoju Guan, Dage Liu, John H.
Reif, & Thomas H. LaBean (2004) Self-Assembled DNA Structures for
Nanoconstruction. International Symposium on DNA-Based Molecular Electronics,
Jena, Germany, May, 2004. Fritzsche, W. eds. AIP Conference Proceedings, 725,
American Institute of Physics. pp. 43-52. [PDF]
198.
John H. Reif,
Sudheer Sahu, Peng Yin, Compact
Error-Resilient Computational DNA Tiling Assemblies, Tenth International Meeting on DNA Based Computers
(DNA10), Milano, Italy, June 7-10, 2004. Lecture Notes in Computer Science
(Edited by C Ferretti, G. Mauri and C. Zandron), Vol.
3384, Springer-Verlag, New York, (2005), pp. 293-307. Published as an invited chapter in text "Nanotechnology: Science and ComputationĶ, Springer
Verlag series in Natural Computing (edited by J. Chen; N. Jonoska and G. Rozenberg), Springer-Verlag Berlin, Germany, pp. 79-104, 2006. [PDF] Talk: [PDF] [PPT]
199.
Peng Yin,
Andrew J. Turberfield, Sudheer Sahu, John H. Reif, Designs for
Autonomous Unidirectional Walking DNA Devices, Tenth
International Meeting on DNA Based Computers (DNA10), Milano, Italy,
June 7-10, 2004. Lecture Notes in Computer Science (Edited by C Ferretti, G.
Mauri and C. Zandron), Vol. 3384,
Springer-Verlag, New York, (2005), pp. 410-425. [PDF] Talk: [PDF] [PPT]
200.
Peng
Yin, Hao Yan, Xiaoju G. Daniel, Andrew J. Turberfield, John H. Reif,
A
Unidirectional DNA Walker Moving Autonomously Along a Linear Track,
Angewandte Chemie [International Edition], Volume 43, Number 37, Sept. 20,
2004, pp. 4906-4911. PubMed PMID:
15372637. [PDF] or [PDF] Supplemental Information: [PDF] Abstract: [PDF] Talk: [PDF] [PPT]
201.
Peng Yin,
Andrew J. Turberfield, John H. Reif, Design of an Autonomous DNA Nanomechanical
Device Capable of Universal Computation and Universal Translational Motion, Tenth International Meeting on DNA Based Computers
(DNA10), Milano, Italy, June 7-10, 2004. Lecture Notes in Computer Science
(Edited by C Ferretti, G. Mauri and C. Zandron), Vol.
3384, Springer-Verlag, New York, (2005), pp. 426-444. [PDF] Talk: [PDF] [PPT]
202.
Peng Yin, Bo
Guo, Christina Belmore, Will Palmeri, Erik Winfree, Thomas H. LaBean, John H.
Reif, TileSoft:
Sequence Optimization Software For Designing DNA Secondary Structures,
Abstract, Preliminary Proceedings, Tenth International Meeting on DNA Based
Computers (DNA10), Milano, Italy, (June 7-10, 2004). [PDF] Talk: [PDF] [PPT]
203.
John H. Reif,
DNA-Based Nano-Engineering: DNA and its Enzymes as the Engines of Creation at
the Molecular Scale, Invited Talk, Abstract, Preliminary Proceedings, Tenth
International Meeting on DNA Based Computers (DNA10), Milano, Italy, (June
7-10, 2004). Abstract: [PDF] Talk: [PDF] [PPT]
204.
John H. Reif, Thomas LaBean, Sudheer Sahu, Hao Yan, Peng Yin, Design,
Simulation, and Experimental Demonstration of Self-Assembled DNA Nanostructures
and DNA Motors, Unconventional Programming Paradigms: International Workshop
UPP 2004, Le Mont Saint Michel, France, September 15-17, 2004. Published by
Springer-Verlag Berlin Heidelberg, edited by Jean-Pierre Bantre, Pascal
Fradet, Jean-Louis Giavitto, Olivier Michel, Lecture Notes for Computer Science
(LNCS) 3566, pp. 173-187, (2005). [PDF] Talk: [PDF] [PPT]
205.
Sung
Ha Park, Hao Yan, John H. Reif, Thomas H LaBean, and Gleb Finkelstein,
Electronic nanostructures templated on self-assembled DNA scaffolds,
Nanotechnology 15 (2004) pp. S525–S527. [PDF]
206.
Sung Ha Park, Peng Yin, Yan Liu, John H. Reif, Thomas
LaBean, and Hao Yan, Programmable DNA
Self-assemblies for Nanoscale Organization of Ligands and Proteins, Nano Letters (Communication), Volume 5, Number 4, pp. 729-733, (2005). PubMed
PMID: 15826117. [PDF]; Supplemental Information: [PDF]
207.
Sung
Ha Park, Robert Barish, John H. Reif, Gleb Finkelstein, Hao Yan and Thomas
LaBean, Three-Helix Bundle DNA Tiles Self-Assemble into 2D Lattice or 1D
Templates for Silver Nanowires, Nano Letters (Communication), Volume 5, Number
4, pp. 693-696 (2005). PubMed PMID:
15826110. [PDF] Supplemental Information: [PDF]
208.
Sung Ha Park,
Constantin Pistol, Sang Jung Ahn, John H. Reif, Alvin R. Lebeck, Chris Dwyer,
and Thomas H. LaBean, Finite-Size, Fully
Addressable DNA Tile Lattices Formed by Hierarchical Assembly Procedures, Angewandte Chemie [International Edition], Volume 45,
Issue 5, pp. 735-739, January 23, 2006. DOI: 10.1002/anie.200503797. [PDF]
209.
John H. Reif,
Sudheer Sahu, and Peng Yin, Complexity
of Graph Self-Assembly in Accretive Systems and Self-Destructible Systems, Eleventh International Meeting on DNA Based
Computers (DNA11), London, Ontario, Canada (June, 2005). Springer-Verlag
Lecture Notes for Computer Science (LNCS), NYC, NY, (edited by Alessandra Carbone and Niles Pierce), Vol. 3892,
Springer-Verlag, New York, (2006), pp. 257-274 [PDF]. Talk: [PPT]
210.
Peng Yin,
Andrew J. Turberfield, John H. Reif, Design of Autonomous
DNA Cellular Automata, Eleventh International
Meeting on DNA Based Computers (DNA11), London, Ontario, Canada (June,
2005). Springer-Verlag Lecture Notes for Computer Science (LNCS), NYC, NY,
(edited by Alessandra Carbone and Niles Pierce), Vol.
3892, Springer-Verlag, New York, (2006),
pp. 399-416 [PDF].
211.
Sudheer
Sahu, Peng Yin and John H. Reif, A Self-Assembly
Model of Time-Dependent Glue Strength,
Eleventh International Meeting on DNA Based
Computers (DNA11), London, Ontario, Canada (June, 2005). Springer-Verlag
Lecture Notes for Computer Science (LNCS), NYC, NY, (edited by Alessandra Carbone and Niles Pierce), Vol. 3892, Springer-Verlag,
New York, (2006), pp. 290-304. Invited Chapter in "Algorithmic
Bioprocesses" (edited by A.Condon, D.Harel, J.N.Kok, A.Salomaa, and
E.Winfree), Published by Springer-Verlag,
ISBN: 978-3-540-88868-0, pp. 185-204 (2009). [PDF] [PDF] Talk: [PPT]
212.
Peng Yin,
Sudheer Sahu, Rizal Hariadi, Harry M. T. Choi, Sung Ha Park, Bethany Walters,
Thomas H. LaBean, John H. Reif, On Constructing Tile-less DNA Ribbons and
Tubes, Abstract, Preliminary Proceedings, 12th International Meeting on DNA
Computing (DNA12), Seoul, Korea (June 5-9, 2006). [PDF] Published as: Peng Yin, Rizal F.
Hariadi, Sudheer Sahu, Harry M.T.Choi, Sung Ha Park, Thomas H. LaBean, John H.
Reif, Programming DNA Tube Circumferences, Science, Vol. 321. no. 5890, pp.
824–826 (August 8, 2008). DOI: 10.1126/science.1157312. [PDF] Supplemental Information: [PDF]
213.
Sudheer Sahu
and John H. Reif, Capabilities and Limits of Compact Error Resilience Methods
for Algorithmic Self-Assembly in Two and Three Dimensions, 12th International
Meeting on DNA Computing (DNA 12), Seoul, Korea, June 5-9, 2006. Published in
DNA Computing: DNA12, Springer-Verlag Lecture Notes for Computer Science (LNCS),
Volume 4287 (edited by Chengde Mao and Takashi
Yokomori), Springer, Berlin Heidelberg, pp. 223-238 (2006). DNA12
Version: [PDF]. Talk: [PPT]. Published in Algorithmica (2008). Full Paper: [PDF] [PDF].
214.
Sudheer Sahu,
Bei Wang, Peng Yin, John H. Reif, A Framework for
Modeling DNA based Molecular Systems, 12th International Meeting on DNA
Computing (DNA 12), Seoul, Korea, June 5-9, 2006. Published in DNA Computing:
DNA12, Springer-Verlag Lecture Notes for Computer Science (LNCS), Volume 4287
(edited by Chengde Mao and Takashi Yokomori),
Springer, Berlin Heidelberg, pp. 250-265
(2006). DNA12 Version: [PDF]. Published as Sudheer
Sahu, Bei Wang, John H. Reif, A Framework for Modeling DNA based Molecular
Systems. Computational and Theoretical Nanoscience, Volume
5, Number 11, pp. 2124-2134(11) (November
2008). Full
Paper: [PDF] Presentation: [PPT]
215.
Urmi Majumder,
Sudheer Sahu, Thomas LaBean, and John H. Reif, Design and Simulation of
Self-Repairing DNA Lattices, 12th International Meeting on DNA Computing (DNA
12), Seoul, Korea, June 5-9, 2006. Published in DNA Computing: DNA12,
Springer-Verlag Lecture Notes for Computer Science (LNCS), Volume 4287 (edited
by Chengde Mao and Takashi Yokomori),
Springer, Berlin Heidelberg, pp.
195–214, (2006). DNA12 Version: [PDF] Poster: [PDF]. Revised Paper submitted for publication as
Urmi Majumder and John H. Reif, Self-Repairing DNA Lattices, (2008). [PDF]
216.
John H. Reif and Sam Slee, Asymptotically Optimal
Kinodynamic Motion Planning for Self-Reconfigurable Robots, Seventh International
Workshop on the Algorithmic Foundations of Robotics (WAFR2006), NYC, New York, July 16-18, 2006. Published in Algorithmic
Foundation of Robotics VII, Springer Tracts in Advanced Robotics (Edited by S.
Akella, N.M. Amato, W.H. Huang, B. Mishra), Volume 47, Springer-Verlag Berlin,
pp. 457–472, (Aug 2008). [PDF] Published as Asymptotically Optimal
Kinodynamic Motion Planning for a Class of Lattice-Style Modular
Self-ReconŪgurable Robots, International Journal of
Computational Geometry & Applications (IJCGA), to appear
(2010). [PDF]
217.
Thomas H.
LaBean, Kurt V. Gothelf, and John H. Reif, Self-assembling DNA Nanostructures
for Patterned Molecular Assembly, invited chapter 5 in textbook
Nanobiotechnology, (edited by Chad A. Mirkin and Christof M. Niemeyer), John
Wiley & Sons Publishers, pp. 79-97, (2007). [PDF]
218.
John H. Reif
and Thomas H. LaBean, Autonomous Programmable Biomolecular Devices Using
Self-Assembled DNA Nanostructures, invited paper, Fourteenth
Workshop on Logic, Language, Information and Computation (WoLLIC'2007), Rio de
Janeiro, Brazil, July 2-5, 2007, Springer-Verlag Lecture Notes for
Computer Science (LNCS), Volume 4576 - 0297, pp. 297-306. Published in Communications of the
ACM (CACM), Special Section entitled ŌNew Computing Paradigms (edited by
Toshinori Munakata), Volume 50, Issue 9, pp. 46-53
(Sept 2007). Short version [PDF] Extended version [PDF] Talk: [PPT] [PDF]
219. Urmi Majumder and John H.
Reif, A
Framework for Designing Novel Magnetic Tiles Capable of Complex Self-Assemblies, Conference on
Unconventional Computation, Vienna, Austria, Aug 25-26, 2008. Published in
Unconventional Computing, Lecture Notes in Computer Science number 105633,
Springer, Berlin Heidelberg. Conference Version: [PDF]. Published as Beyond
Molecular Computing:
Novel Magnetic Tiles for Complex Assemblies, Invited paper, special issue "Computing with Molecules" of Natural Computing,
(2009). Full Paper: [PDF]
220. John H. Reif and Thomas H. LaBean, DNA Nanotechnology and its Biological Applications. In book ŌBio-inspired
and Nanoscale Integrated ComputingĶ, Chapter 13, pp. 349-375 (edited by
Mary Mehrnoosh Eshaghian-Wilner), Publisher: Wiley, Hoboken, NJ, USA,
(February
2009). [PDF]
221.
Ashish Gehani
and John H. Reif, Parameterizing Super-resolution Forensic Analysis of Video,
3rd IFIP International Conference on Digital Forensics, Orlando, FL, Jan 28-31,
2007. Published as Super-Resolution Video Analysis for Forensic Investigations,
Advances in Digital Forensics, Chapter 15, Volume 32007, pp. 228-229. [PDF]
222.
John H. Reif
and Sam Slee, Optimal Kinodynamic Motion Planning for Self-ReconŪgurable Robots
Between Arbitrary 2D ConŪgurations, Robotics: Science and Systems Conference,
Georgia Institute of Technology, Atlanta, GA, June 27-30, 2007. [PDF]
223. John H. Reif and Sudheer Sahu,
Autonomous Programmable DNA Nanorobotic Devices Using DNAzymes, 13th International Meeting
on DNA Computing (DNA 13), Memphis,
Tennessee,
June 4-8, 2007. In DNA Computing: DNA13 (edited by Max Garzon and Hao Yan), Springer-Verlag Lecture Notes for Computer Science
(LNCS), Springer, Berlin Heidelberg, Volume 4848, pp. 66-78 (2008). DNA13 Version: [PDF] Talk: [PDF]. Published
in Special Journal Issue on Self-Assembly, Theoretical
Computer Science (TCS), Vol 410, Issue 15, pp. 1428-1439 (April 2009). Full
Paper: [PDF] [PDF].
224.
Urmi
Majumder, Thomas H LaBean, and John H. Reif, Activatable Tiles for Compact Error-Resilient Directional Assembly.
13th International Meeting on DNA Computing (DNA 13), Memphis, Tennessee, June
4-8, 2007. Published as Activatable Tiles: Compact, Robust Programmable
Assembly and Other Applications, in DNA Computing: DNA13 (edited by Max Garzon
and Hao Yan), Springer-Verlag Lecture Notes for Computer Science (LNCS),
Springer, Berlin Heidelberg, Volume 4848, pp. 15-25. Conference Version: [PDF] Full Paper: [PDF]. Talk: [PPT]
225.
Urmi Majumder,
John H. Reif, and Sudheer Sahu, Stochastic Analysis of Reversible Self-Assembly.
Journal of Computational and Theoretical Nanoscience, Volume 5, Number 7, pp.
1289-1305, July 2008. Full Paper: [PDF] [PDF].
226.
John H. Reif,
Mechanical Computation: itÕs Computational Complexity and Technologies, invited
chapter, Encyclopedia of Complexity and System Science (edited by Robert A. Meyers),
Springer (2009) ISBN: 978-0-387-75888-6. [PDF]
227.
John H. Reif and Urmi Majumder, Isothermal Reactivating
Whiplash PCR for Locally Programmable Molecular Computation, Fourteenth International Meeting on DNA Based Computers (DNA14), Prague, Czech Republic (June, 2008). Lecture Notes for Computer
Science (LNCS), NYC, NY, (edited by Ashish Goel and
Friedrich C. Simmel), Springer-Verlag, New York, (2009). Conference Version: [PDF] Talk: [PDF] [PPT]. Invited Paper, Special
issue in Natural Computing, Springer
Netherlands,
ISSN: 1567-7818 (Print) 1572-9796
(Online),
DOI: 10.1007/s11047-009-9148-6 (August, 2009). Full Paper: [PDF]
228.
Sudheer Sahu,
Thomas H. LaBean and John H. Reif, A DNA Nanotransport Device Powered by
Polymerase ϕ29, Nano Letters, 2008, 8 (11), pp 3870–3878,
(October, 2008) DOI: 10.1021/nl802294d. [PDF] [PDF] supplementary material: [PDF]
229.
Thomas
H. LaBean, Geetha Shetty, Hao Yan, Erik A. Schultes, Harish Chandran, John H.
Reif, Target DNA Detection by Strand Displacement and Deoxyribozymogen
Amplification, abstract, FNANO 2009, Snowbird, Utah,
Sciencetechnica, pp. 60-61 (April 2009). [PDF]
230.
Thomas
H. LaBean, Geetha Shetty, Peng Yin, Erik A. Schultes, Harish Chandran, John H.
Reif, A Dendritic Nanostructure for DNA Detection, abstract,
FNANO 2009, Snowbird, Utah,Sciencetechnica, pp. 82-83 (April 2009). [PDF]
231.
Bishop M, Thiem C, Renz T,
Schultes EA, Chandran H, Reif JH (2009) Structural Optimization of Dendritic
DNA Self-Assembly, abstract, FNANO 2009, Snowbird, Utah, Sciencetechnica, pp.
147-148 (April 2009). [PDF]
232.
Harish
Chandran Nikhil Gopalkrishnan, and John Reif, The Tile Complexity of Linear
Assemblies, 36th International Colloquium on Automata, Languages and
Programming (ICALP 2009), July 5 - 12, 2009, Rhodes, Greece, Proceedings Part I
(edited by Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris
Nikoletseas, and Wolfgang Thomas), Lecture Notes in Computer Science,
Springer-Verlag, Berlin, pp. 235-253 (2009). [PDF] Talk: [PPT] [PDF]
233.
John
H. Reif and Thomas H. LaBean, Engineering Natural Computation by Autonomous DNA-Based
Biomolecular Devices,
Invited Chapter, Handbook
of Natural Computing, edited by
Grzegor Rozenberg, Thomas Bck, Joost Kok, Springer-Verlag, New York, (2009). [PDF]
234.
John H. Reif
and Urmi Majumder, Design of a Biomolecular Device that
Executes Process Algebra, Fifteenth
International Meeting on DNA Computing and Molecular Programming (DNA15), Fayetteville,
Arkansas (June 8-11, 2009). Lecture Notes for Computer Science (LNCS),
NYC, NY, (edited by Russell Deaton and Jin-Woo Kim), Springer-Verlag,
New York, (2010). Conference Version: [PDF] Talk: [PDF] [PPT].