CURRICULUM VITAE

John H. Reif

Personal

John Henry Reif

Born: 1951

Madison, Wisconsin

U.S. Citizen 

Current Position

Hollis Edens Professor, Trinity College of Arts and Sciences, Duke University since 2003.

Professor of Computer Science at Duke University, since 1986.

Academic Address Home Address

D223 LSRC Building 3112 Devon Road

Dept. of Computer Science Durham, NC 27707

Duke University

Durham, NC 27708-0129 U.S.A.

Office phone: home phone:

(919) 660-6568 (919) 493-7978

Email Address:

Homepage: http://www.cs.duke.edu/~reif

Research Interests - DNA nanostructures, Molecular Computation, Efficient Algorithms, Parallel Computation, Robotic Motion Planning, and Optical Computing.

Recreational Interests - skiing and cross-country skiing, wind surfing, canoeing and hiking

Education

Ph.D. in Applied Mathematics (Division of Applied Sciences, Harvard University, Cambridge, MA, July 1977) Thesis title: Combinatorial Aspects of Symbolic Program Optimization. Thesis advisor: Harry R. Lewis (Previously Dean of Harvard College)

M.S. in Applied Mathematics (Division of Applied Sciences, Harvard University, Cambridge, MA, Spring 1975)

B.S., magna cum laude, in Applied Mathematics and Computer Science, (Tufts University, Medford, MA, Spring 1973)

Enrolled in independent study in mathematics, computation and optics during Fall 1970 - Spring 1973, funded by a grant from the Sloan Foundation's Unified Science Study Program.

Note: While an undergraduate Fall 1970 - Spring 1973 at Tufts U., Reif was in the Unified Science Study Program(USSP), an interdisciplinary independent study program (spanning mathematics, computer science, physics, and engineering disciplines) funded by a grant from the Sloan Foundation. His undergraduate projects were funding under this program and included: stochastic analysis and computer simulations of neural nets, design of computer made holograms, software for structural analysis of geodesic domes, and a computer generated short animated movie. Reif was given a full scholarship and graduated from Tufts in 3 Years with a magna cum laude award.

Wellesley High School, Wellesley, MA, Spring 1970

Faculty Positions

A. Hollis Edens Distinguished Professor of Computer Science in Trinity College of Arts and Sciences, Duke University, September 1, 2003 to present.

Professor, Duke University, Summer 1986 to present

Visiting Professor (Sabbatical), Carnegie Mellon University, Spring 1994.

Visiting Scientist, Mathematical Sciences Research Institute, Berkeley, CA, Spring 1986

Associate Professor, Harvard University, Spring 1983 to Spring 1986

Visiting Scientist (Sabbatical), Laboratory for Computer Science at M.I.T., Fall 1984

Assistant Professor, Harvard University, Fall 1979 to Spring 1983

Assistant Professor, University of Rochester, New York, Fall 1978 to Spring 1979

Research Associate, University of Rochester, New York, Fall 1977 to Fall 1978

(Research Assistant, Harvard University, Spring 1975 to Spring 1977)

Memberships, Awards and Prizes

Fellow: Association for the Advancement of Science (AAAS), since 2003.

Fellow: Association for Computing Machinery (ACM), since 1997.

Fellow: Institute of Electrical and Electronics Engineers (IEEE) since 1993.

Fellow: Institute of Combinatorics and its Applications, since 1991.

Awarded: "DNA Computing Tulip Prize" by the 2005 International Meeting on DNA Based Computers.

Awarded: Harvard University Thomas Hoopes Prize for directing the undergraduate honors thesis, by Philip N. Klein (now Full Professor, Brown University), $500 in research funds, June 1984.

Member: Faculty of 1000, since 2005

Member: International Society for Nanoscale Science, Computation and Engineering (ISNSCE) Chair of Scientific Advisory Committee of ISNSCE since 2004.

Member: Society of Industrial and Applied Mathematicians (SIAM)

Member: American Mathematics Society(AMS)

Member: Sigma Xi Scientific Research Society

Listed: Highly Cited Researcher, Computer Science, Thompson ISI

Listed: Who's Who in America, Who's Who in the World, Who's Who in Emerging Leaders in America, Who's Who in Science and Engineering, Who's Who in American Education.

Courses Taught

Fall, 2008, Analysis of Algorithms, CPS 130, Duke University.

Spring, 2008, Randomized Algorithms, CPS 237, Duke University.

Fall, 2007, Analysis of Algorithms, CPS 130, Duke University.

Spring, 2007, Computational Complexity, CPS 240, Duke University.

Fall, 2006, Analysis of Algorithms, CPS 130, Duke University.

Spring, 2006, Randomized Algorithms, CPS 237, Duke University.

Fall, 2005, Analysis of Algorithms, CPS 130, Duke University.

Summer, 2005, Analysis of Algorithms(NCSC 6021). Taught this masters-level remote instructional course for National Technical University(Walden University), produced at MGM Studios, Orlando, FL, June, 2005.

Spring, 2005, Analysis of Algorithms, CPS 130, Duke University.

Fall, 2004, Efficient Algorithms, CPS 230, Duke University.

Spring, 2003, Analysis of Algorithms, CPS 130, Duke University.

Fall, 2002, Efficient Algorithms, CPS 230, Duke University.

Spring, 2002, Randomized Algorithms, CPS 237, Duke University.

Fall 2001, Analysis of Algorithms, CPS 130, Duke University.

Spring 2001, Mathematical Foundations of Computer Science, CPS 140, Duke University.

Fall 2000, Computational Biology, CPS 296.2, Duke University.

Spring 2000, Computational Biology and Biomolecular Computation, CPS 296.2, Duke University.

Fall 1999, Analysis of Algorithms, CPS 130, Duke University.

Spring 1999, Analysis of Algorithms, CPS 130, Duke University.

Fall 1998, Parallel Algorithms, CPS 236, Duke University.

Spring 1998, Analysis of Algorithms, CPS 130, Duke University.

Fall 1997, Design and Analysis of Algorithms, CPS 230, Duke University.

Spring 1997, Analysis of Algorithms, CPS 130, Duke University.

Fall 1996, Design and Analysis of Algorithms, CPS 230, Duke University.

Spring 1996, Parallel Algorithms, CPS 236, Duke University.

Fall 1995, Analysis of Algorithms, CPS 130, Duke University.

Spring 1995, Parallel Algorithms, CPS 236, Duke University.

Fall 1994, Analysis of Algorithms, CPS 230, Duke University.

Fall 1993, Analysis of Algorithms, CPS 174, Duke University.

Spring 1993, Parallel Algorithms, CPS 230, Duke University.

Fall 1992, Analysis of Algorithms, CPS 174, Duke University.

Spring 1992, Numerical and Algebraic Algorithms, CPS 206, Duke University.

Fall 1991, Parallel Algorithm Implementation, CPS 265, Duke University.

Spring 1991, Computational Robotics, CPS 265, Duke University.

Fall 1990, Analysis of Algorithms, CPS 174, Duke University.

Spring 1990, Advanced Topics in Theory, CPS 265, Duke University.

Fall 1989, Analysis of Algorithms, CPS 224, Duke University.

Spring 1989, Advanced Topics in Massively Parallel Processing, CPS 265, Duke University.

Spring 1989, Advanced Topics in Algorithms, CPS 265, Duke University.

Fall 1988, Analysis of Algorithms, CPS 174, Duke University.

Spring 1988, Parallel Algorithms, CPS 265, Duke University.

Fall 1987, Analysis of Algorithms, CPS 224, Duke University.

Spring 1987, Parallel Algorithms, CPS 265, Duke University.

Fall 1986, Analysis of Algorithms, CPS 224, Duke University.

Spring 1994, Algorithms for Scientific Computation CS 15-850, Carnegie-Mellon University.

Fall 1985, Introduction to the Theory of Computing, CS 207, Harvard University.

Spring 1985, The Complexity of Computations: Parallel Computation, CS 224, Harvard University.

Spring 1984, The Complexity of Computations: Parallel Computation, CS 224, Harvard University.

Fall 1983, Efficient Algorithms, CS 226, Harvard University.

Spring 1983, The Complexity of Computations: Parallel Computation, AM 224, Harvard University.

Fall 1982, Efficient Algorithms, AM 226, Harvard University.

Spring 1982, The Complexity of Computations: Parallel Computation, AM 224, Harvard University.

Fall 1981, Introduction to the Theory of Computing, AM 207, Harvard University.

Spring 1981, Data Structures, AM 119, Harvard University.

Fall 1980, Introduction to the Theory of Computing, AM 207, Harvard University.

Spring 1980, Introduction to the Theory of Computing, AM 207, Harvard University.

Fall 1979, Efficient Algorithms, AM 226, Harvard University.

Spring 1979, Seminar in Research Topics, CSC 589, University of Rochester.

Fall 1978, Introduction to Theory of Computation, CSC 281/481, University of Rochester.

Fall 1978, Programming Problems Seminar, CSC 400, University of Rochester.

Spring 1978, Seminar on Optimization of Computer Programs, CSC 589, University of Rochester.

Fall 1977, Programming Problems Seminar, CSC 400, University of Rochester.

Postdoc Supervision

Xiaoju Guan (jointly supervised with Hao Yan), 2003-2005.

Sang Jung Ahn (jointly supervised with Thom LaBean), 2003- December, 2004. (Currently Research Scientist, Korea Research Institute of Standards and Science, Daejeon, South Korea)

Dage Liu, Postdoc 2001-2004 (currently Research Associate, Department of Chemistry, North Carolina State University)

Hao Yan, Postdoc 2001-2002 and Research Assistant Professor, CS Dept, Duke University, 2002-2004 (now Professor, Chemistry and Biochemistry Department, Arizona State University since August 2004)

Thom LaBean, Postdoc 1998-2001 (currently Research Associate Professor, CS Dept, Duke University)

Sandeep K. S. Gupta, Postdoc 1995 (currently Professor, Department of Computer Science and Engineering, Ira A. Fulton School of Engineering, Arizona State University, Tempe, AZ 85287-5406).

Peter Mills, Postdoc 1993-1996 (currently President & CEO, Orielle, LLC, Moscow, Idaho)

Lars Nyland, Postdoc 1991-1991 (Currently Senior Architect, NVIDIA, Durham, NC and Adjunct Associate Professor, Department of Computer Science, University of North Carolina, Chapel Hill, NC.)

Steven Tate, Postdoc 1991-1993 (currently Professor and Chairman, Department of Computer Science, University of North Carolina at Greensboro, Greensboro, NC)

Hillel Gazit, Postdoc 1989-1991

Paul Spirakis, Postdoc 1982-1982 (Currently Full Professor and Chairman, Department of Computer Engineering & Informatics, University of Patras, School of Engineering, Patras, Greece and Director Computer Technology Institute, Patris, Greece.)

Current Graduate Students (Ph.D. candidates)

Harish Chandran, Ph.D. thesis topic: “Molecular Robotic Devices”. Projected Date of Graduation: Spring 2011.

Nikhil Gopalkrishnan, Ph.D. thesis topic: “DNA Self-Assembly”. Projected Date of Graduation: Spring 2010.

Samuel Slee, Ph.D. thesis topic: “Asymptotically Optimal Kinodynamic Motion Planning for Self-Reconfigurable Robots”. Projected Date of Graduation: Spring 2009.

Graduate Student Supervision (Completed Degrees):

Urmi Majumder (also co-advised by Thomas LaBean), Ph.D. thesis: “Molecular Computing with DNA Self-Assembly”. March 30, 2009. [PPT] [PDF]

Sudheer Sahu, Ph.D. thesis: “DNA based self-assembly and nanorobotics: Theory and Experiments”, December, 2007 [PDF] Slides: [PPT] [PDF]. (Currently Research Scientist, Microsoft Live Search, in Redmond, Washington)

Peng Yin, Ph.d thesis: Theoretical and Practical Study in DNA Based Self-Assembly, Nanorobotics, and Nanocomputation. May, 2005 [PDF] [abstract] Slides: [PPT] [PDF]. (2005-2009, CPI Postdoctoral Researcher, Caltech, Pasadena, CA), (currently Assistant Professor, Department of Systems Biology, Harvard Medical School, Cambridge, MA).

Sung Ha Park, Ph.D. thesis: “Self-assembled DNA Nanostructures and DNA-templated Silver Nanowires” Thesis: [PDF] Slides: [PPT] [PDF] (Reif was secondary adviser only; primary supervisors are Thom LaBean and Gleb Finkelstein (Dept of Physics), Department of Physics, May, 2005 (2005-2007, CPI Postdoctoral Researcher, Caltech, Pasadena, CA), (Currently Assistant Professor, Sungkyunkwan University, South Korea).

Zhung(Robert) Sun, Duke University Ph.D. thesis: Complexity of Robotic Movement Problems. Date of Graduation: April 2003 [PDF] [abstract] Slides: [PPT] [PDF]. Masters Thesis "The Computational Power of Frictional Mechanical Systems, May, 1999. (Currently Research Scientist, Google Inc., 1600 Amphitheatre Parkway, Mountain View, CA 94043. Email: sunzheng@gmail.com)

Guo Bo, Duke University Master Thesis "Computing by DNA Self-Assembly". Oct, 2001 (currently Research Scientist, Mitsubishi Electric, Japan).

Yuan Guangwei, Duke University Master Thesis "Simulation of DNA Self-Assembly", Fall 2000 (Currently Research Scientist, China).

Christopher Butler, Duke University Master Thesis "Simulations of Molectronics architectures", 2000.

Xavier Berni: MS Thesis "DNA tagging", May 2000. (Currently Computer Scientist Consultant, S. Carolina)

Deganit Armon, Ph.D. Thesis "Dynamic Data Structures for Randomized Algorithms that use Sampling", 1997. Thesis: [PDF] [abstract] (Adjunct Professor, Department of Computer Science & Engineering, University of California, Riverside and Project Manager at Advatech Pacific, Inc.)

Ashish Gehani, Masters Thesis "Image Resolution Enhancement via Data Compression Techniques", 1997 (Currently Research Assistant Professor, Department of Computer Science and Engineering, University of Notre Dame).

Shenfeng Chen, Ph.D. Thesis "Algorithmic Applications of Data Compression Techniques", 1996. Thesis: [PDF] [abstract]. (Currently Technical Manager of a startup company in China).

Hongyan Wang, Ph.D. Thesis “Approximate and Adaptive Algorithms for Some Optimal Motion-Planning Problems,” 1996 Thesis: [PDF] [abstract] (Previously senior software engineer with Parametric Technology Corporation in Massachusetts and with Canopus, Ltd. in Kobe, Japan. Currently Adjunct Faculty member of University of Maryland University College, Asia).

Zhiyong Li, Ph.D. Thesis "Computational Models and Program Synthesis for Parallel Out-of-Core Computation", May, 1996 [PDF] [abstract]. (Currently Research Scientist, Sun Microsystems, California)

Akitoshi Yoshida, Ph.D. Thesis "Applications of Optical Techniques in Interconnections, Image/Video Compression, and Computational Geometry", 1994, Univ. Microfilms Int. 9424616 [abstract] (Currently Research Scientist, Computing Center of the University of Mannheim, Germany, yoshida@rz.uni-mannheim.de).

Salman Azhar (J.P. Duke Fellow as Graduate Student), Ph.D. Thesis "Computational Aspects of Multiagent Systems: Modeling Efficiency and Computing Sequential Equilibrium", 1993, Univ. Microfilms Int. 9420402 [abstract]. Masters Thesis "Efficient Learning of Permutation Groups by Examples", 1990 (Currently Executive Consultant at Eike Consulting, LLC and Advisor (2008-present) & VP Engineering (2006-08) at DecisionStreet, Inc. Previously Associate Professor at University of San Francisco.)

Peter Su, Dartmouth University Ph.D. Thesis (Ph.D. completed at Duke but Scott Drysdale was official Supervisor) "Efficient Parallel Algorithms for Closest Point Problems", 1994 Univ. Microfilms Int. 9524419 (Previously Research Assistant Professor, Software Institute, Carnegie Mellon University.)

Tassos Markas, Ph.D. Thesis "Data Compression: Algorithms and Architectures", 1993, Univ. Microfilms Int. 9405986 [abstract]. (Currently Director of Multimedia, Atmel Corporation, San Jose, CA. Previously Research Scientist, VLSI Design and Test Department, Center for Digital Systems Engineering, Research Triangle Institute, RTP, NC.

Steven Tate, Ph.D. Thesis "Arithmetic Circuit Complexity and Motion Planning", 1991, Univ. Microfilms Int. 9127527 [abstract]. (Currently Professor and Chairman, Department of Computer Science, University of North Carolina at Greensboro, Greensboro, NC.)

Lars Nyland, Ph.D. Thesis "The Design of a Prototyping Programming Language for Parallel and Sequential Algorithms", 1991, Univ. Microfilms Int. 9127499 [abstract]. (Currently Senior Architect, NVIDIA, Durham, NC and Adjunct Associate Professor, Department of Computer Science, University of North Carolina, Chapel Hill, NC.)

Sandeep Sen, Ph.D. Thesis "Random Sampling Techniques for Efficient Parallel Algorithms in Computational Geometry", 1989, Univ. Microfilms Int. 9025050 [PDF] [abstract] (Currently Full Professor and Chairman, Department of Computer Science & Engineering, Indian Institute of Technology, Delhi, India).

Sanguthevar Rajasekaran, Harvard University Ph.D. Thesis "Randomized Parallel Computation", 1988, Univ. Microfilms Int. 8909005. (Currently UTC Chair Professor of CSE and Director of the Booth Engineering Center for Advanced Technologies (BECAT), Computer Science and Engineering Department, University of Connecticut.)

Paul Spirakis, Harvard University Ph.D. Thesis "Probabilistic Algorithms", Dec. 1981, University Microfilms International No. 8216206. (Currently Full Professor and Chairman, Department of Computer Engineering & Informatics, University of Patras, School of Engineering, Patras, Greece and Director Computer Technology Institute, Patris, Greece.)

Undergraduate Thesis Supervision

Philip Klein; Harvard University Undergraduate Thesis(awarded Thomas T. Hoopes priz) "Stacktracking: Parallel Acceptance of Deterministic Context-Free Languages", 1984 (Currently Full Professor, Brown University).

Research Support: Principal Investigator or Co-Investigator

NSF EMT Grant CCF-0829797: EMT/NANO: Autonomous Programmable DNA Devices Using DNAzymes (PI John H. Reif), 09/4/2008-08/31/2011 $200,000.00.

NSF EMT Grant CCF-0829798: EMT/NANO: Polymerase-Based Self-Activating and Reactivating DNA Systems, (PI John H. Reif with coPI Thomas H. LaBean), 09/01/2008-08/31/2009, $200,000, with expected continued support for 2009 and 2010 for $150,000/year.

AFSOR Contract FA9550-08-1-0188, Bio-X-AFSOR: Encapsulated DNA-Based Molecular Autonomous Sensing Devices With Photonic Output (PI John H. Reif), April, 2008-Dec 2008, $200,000

NSF EMT Grant CCF-0551965: EMT: NSF Workshop: Emerging Opportunities of Nanoscience to Energy Conversion and Storage (PI John H. Reif), September 1, 2005- September 1, 2006, $49,900. http://www.cs.duke.edu/~reif/NSF.NanoEnergy/

NSF EMT Grant CCF-0523555: EMT: A DNA-Based Autonomous Programmable Molecular Transport Network (PI John H. Reif with coPI Thomas H. LaBean), July 15, 2005- August 31, 2007, $300,000 (anticipated to be renewed in FY2007 for $100,000/year).

NSF EMT Grant CCF-0523558: EMT: NSF Workshop of Programmed Self-Assembly (PI John H. Reif), May. 1, 2005-October 31, 2005, $30,000.

NSF EMT Grant CCF-0432038: Nano: Error-Resilient DNA Tiling Assemblies (PI John H. Reif with coPI Thomas H. LaBean), Sept. 1, 2004-Aug. 30, 2007, $295,000.

NSF EMT Grant CCF-0432047: NANO: Combinatorial Self-assembly of Nanocircuits on Addressable DNA Nanoscaffolds (PI Hao Yan with coPIs: Chris L. Dwyer, Gleb Finkelstein, John H. Reif, Thomas LaBean), Sept. 1, 2004-Aug. 30, 2005, $100,000. (anticipated to be renewed in FY2005 and FY2006 for $100,000/year)

Taiko Denki Inc. Industrial Grant: Applications of DNA Self-Assembly Nanofabrication Technology to Molecular Scale Electrical Contacts (PI John H. Reif with coPI Thomas H. LaBean), Taiko Denki Inc., Tokyo, Japan, Jan. 1, 2004-Dec. 30, 2004, $55,000.(renewable in FY2005 for $55,000).

NSF ITR 0326157: Nanoarchitecture: Balancing Regularity, Complexity and Defect Tolerance using DNA for Nanoelectronic Integration(PI: Alvin LeBeck CoPIs: Dan Sorin, Jie Liu, John H. Reif, Thom LaBean, Hao Yan, Sean Washburn, Dorothy Erie, Paul Franzon), Sept 1, 2003- Aug 31, 2006. $1,200,000.

NSF QuBIC EIA-0218376: Novel DNA Nanostructures for Targeted Molecular Scale to Micro Scale Interconnects. (PI: Thomas H. LaBean, CoPI: John H. Reif) NSF EIA-0218376, Sept 1, 2002- Aug 31, 2005. $349,999.

NSF EIA-0218359: Molecular Robotics for DNA Nanostructures. (PI: Hao Yan, CoPI: John H. Reif), Sept 1, 2002- Aug 31, 2005. $349,995.

Taiko Denki Inc. Industrial Grant: DNA Self-Assembly Nanofabrication Technology to Molecular Scale Electrical Contacts (PI John H. Reif with coPI Thomas H. LaBean), Taiko Denki Inc., Tokyo, Japan, Sept. 1, 2002- Sept. 30, 2003, $60,000.

Programmable DNA Lattices: Design, Synthesis and Applications (PI John H. Reif), BioComp Program, DARPA/AFSOR Contract, F30602-01-2-0561 July 1, 2000-Dec 30, 2004, $2,550,000.

Supplemental Augmentation to: Programmable DNA Lattices: Design, Synthesis and Applications (PI John H. Reif), BioComp Program, DARPA/AFSOR Contract, F30602-01-2-0561 Jan 1, 2002-Dec 30, 2002, $112,662 for FY2002.

Micro and Nano-Robotics Motion Control Algorithms (PI John H. Reif), NSF SEGR Award NSF-11S-01-94604, Sept 1, 2000-Sept 30, 2001, $80,772.

NSF ITR Grant EIA-0086015: Supplemental Augmentation to: Self-Assembly of DNA Nano-Scale Structures for Computation (PI John H. Reif), additional $413,000 awarded in FY 2004.

NSF ITR Grant EIA-0086015: Self-Assembly of DNA Nano-Scale Structures for Computation, (PI John H. Reif), Sept 1, 2000-Sept 30, 2005, $2,019,999. (awarded $1,184,999 September 1, 2000-August 31, 2003, with additional $413,000 awarded in FY 2004, and $422,000 projected in FY 2005.)

Prototyping Biomolecular Computations, (PI John H. Reif), jointly funded by Defense Advanced Research Projects Agency and National Science Foundation, NSF CCR-9725021, July 1997-Sept 2001, $2,748,017.

Moleware and the Molecular Computer, Subcontract PI (overall PI: James M. Tour), DARPA/ONR N00014-99-1-0406, 01 Mar 99 through 28 Feb. 2001, Subcontract $50,000.

Robust, Adaptive and Dynamic Robotic Motion Planning, (PI John H. Reif), NSF Grant NSF-IRI-9619647, 5/97-06/2000, $295,000.

SEGR: Design of a Biomolecular Distributed Operating System, (PI John H. Reif), NSF Grant CCR-9810000, Aug 1998-1999, $50,000.

CURIOUS: (C)enter for (U)ndergraduate Education and (R)esearch: (I)ntegration Thr(OU)gh Vi(S)ualization, (Co-principal investigator). NSF CDA-96-34475 09/96 - 08/99 $ 405,200

Acquisition of a Workstation Cluster Testbed for Next-Generation Collaborative Computing (Co-principal investigator). National Science Foundation Grant contract CDA-95-12356, 09/95 - 08/98, $489,600

Multidisciplinary Research for Demining, (Co-principal investigator of subcontract with E. Gelenbe, N Schmajuk and J. Staddon,) Army Research Office(ARO) contract DAAH-04-96-1-0448, 11/96 - 10/99, total contract: $3,000,600, Subcontract $431,000./year.

An Exploratory Study of Parallel Molecular Computation, (PI John H. Reif) National Science Foundation Grant number CCR-96-33567, 08/96 - 07/97 $50,000

Toward Autonomous Robots: Robust, Adaptive and Dynamic Motion Planning, (PI John H. Reif), National Science Foundation Grant NSF-IRI-91-00681,02/92 - 01/97, $365,755,

SIMD/MIMD Parallel Computing: Computational Theory, Scientific Applications, and Systems Research, (Co-principal investigator with C.S. Ellis, C. Gardner, H.S. Greenside, D.W. Loveland, and D.J. Rose) National Science Foundation Grant number CDA-91-23483, CISE Institutional Infrastructure Program, 09/92 - 08/98, $1,420,001 plus institutional support of $421,209.

A Refinement-Based Methodology for the Architecture-Independent Design and Development of Parallel Software, (Co-principal investigator with A. Goldberg and J. Prins). Rome Laboratory contract F30602-94-C-0037, Subcontract to Kestrel Development Corporation, $314,495.

Common Prototyping Language (CPL) based on SETL, REFINE, and UNITY, DARPA/ISTO contract N00014-92-C-0182 under subcontract KI-92-01-0182 from Kestrel Institute, Additional $665,147, September 1, 1992 through August 31, 1995

Common Prototyping Language (CPL) based on SETL, REFINE, and UNITY, DARPA/ISTO, Subcontracted from Kestrel Institute, Additional $240,000, May 1, 1991-March 30, 1992.

Derivation and Analysis Tools for the Synthesis and Implementation of Parallel Algorithms, (PI John H. Reif), DARPA/ISTO contract N00014-91-J-1985, $1,560,000, July 1, 1991-June 30, 1994.

Parallel Compression of Space and Earth Data, (PI John H. Reif), NASA, Prime Contract Number: NAS5-30428, Subcontract 550-63, $491,699, October 1, 1991-September 30, 1993.

Randomized Methods in Distributed and Parallel Computation, (with B. Chor), Binational Science Foundation, $36,000, September 1, 1989-August 31, 1992.

Common Prototyping Language (CPL) based on SETL, REFINE, and UNITY, DARPA/ISTO, Subcontracted from Kestrel Institute, $162,240, October 1, 1989-September 30, 1990.

Very High Speed Holographic Message Routing for Parallel Machines, (PI John H. Reif), DARPA/ARMY, $290,673, September 1, 1988-August 31, 1990.

Parallel Compression of Space and Earth Data, (PI John H. Reif), NASA, $435,000, October 1, 1988-September 30, 1991.

Parallel Algorithm Derivation, (PI John H. Reif), DARPA/ISTO, $696,899, July 1, 1987-June 30, 1991.

Computational Complexity and Efficiency in Electro-optical Computing Systems, (PI John H. Reif), Air Force Office of Scientific Research, $442,772, September 1, 1987-August 31,1990.

Randomized Parallel Algorithms in Learning, (PI John H. Reif), Office of Naval Research, $228,707, January 1, 1987-February 28, 1989.

Randomized Techniques for Highly Parallel Computing, (PI John H. Reif), Office for Naval Research, $93,475, July 1, 1984-June 30, 1986.

Parallel and Probabilistic Computations, (Co-Investigator with H. R. Lewis) National Science Foundation, $113,455, July 1, 1982-December 31, 1984.

Distributed Multi-processing, (PI John H. Reif), Office for Naval Research, $132,000, July 1, 1980 -June 30,1984.

Graph Algorithms in Program Analysis and Topological Imbeddings, (PI John H. Reif), National Science Foundation, $25,000, October 1, 1979-July 31, 1982.

Experimental Projects: Hardware, Software and Biochemistry

1. (Current) President of Eagle Eye, Inc., a small business based in the Research Triangle, NC. It was originally engaged in reconnaissance multi-spectral image target recognition. EagleEye, Inc. now specializes in contract research in the areas of defense applications of DNA biotechnology. Eagle Eye, Inc. has executed a number of federal research contracts over the last three years. In 2000, Eagle Eye developed (in collaberation with M. Pirrung, Dept of Chemistry, Duke Univ.) a biomolecular system for associative search in pedabit size DNA libraries.

2. DNA Tagging Project(with C. X. Berni, C. Kingsford) We made improvements to SAGE tagging to allow the technology to be applied to universal DNA hybridization arrays. Also, developed simulation software for the improved tagging process with a highly interactive graphic interface.

3. (Previous) Chief scientist of Rtware, 1995-1999, which produces real-time control software which is currently used for both commercial and military applications; military customers include the Airforce and Navy. RTware has received a Phase I SBIR from ONR, It was bought out by Datacode (a large hardware corporation) in 1999.

4. (Previous) President of RSIC Associates, which received a Phase I and Phase II NASA Small Business Innovation Research Grant to build very high rate (.20 gigabit/second) lossless data compression hardware system that was successfully demonstrated. The multiprocessor chip (1.2 micron CMOS with approx. 330,000 transistors and with 128 specialized systolic processor cells per chip) was been fabricated and tested. A number of compression boards, each containing 16 of these chips, have been running since spring, 1992 and can be used by remote login to MCNC. In collaboration with Professor Jim Storer of Brandeis University. VLSI design by Research Triangle Institute, Research Triangle Park, NC in 1989. Board Level Design by MCNC, NC. Also funded by DARPA/ISTO for MOSES fabrication by HP. RSIC Associates has received contracts totaling $1,200,000 from various defense agencies, for the development of this hardware.

5. Co-architect of BLITZEN (with Ed Davis), a 16,000 processor Massively Parallel Machine under NASA contract at Microelectronics Center of North Carolina (MCNC). The main component of the system was a BLITZEN chip, consisting of 128 bit serial processors (.25 gigabits/second). This chip is 1.2 micron CMOS and has 1,100,000 transistors, making it the largest (nonmemory) chip manufactured in the world during early 1989. The chip is tested and functional. A prototype BLITZEN system has been running since spring, 1989. See Publications (references #73,76).

6. Inventor of Holographic Based Message Routing Systems for Massively Parallel Machines. The prototype was constructed under DARPA Contract by Kristina Johnson at the Center for Electro-Optical Computing Systems, Boulder, CO, April 2, 1989. See Publications (reference #80).

7. Implementation (in collaboration with Charles Leiserson, Jill Mesirov, Lena Nekluvova, Steven Omohandro, and Washington Tayler) of Parallel Nested Dissection Algorithms for Solution of Large Sparse Linear Systems on the 64,000 process Connection Machine. Thinking Machines, Inc., Cambridge, MA, 1985-1986. See Publications (reference #62).

8. Implementation (in collaboration with John Dorband and Torstein Opsahl) of Parallel Nested Dissection on 16,000 Processor Massively Parallel Processing Machine (MPP), NASA Goddard Space Center, Greenbelt, MD, 1985-1986. See Publications (reference #63).

Legal: Expert Witness and Legal Consulting Positions

1. Member of Round Table Fellowship, a senior subgroups of consultants for the Round Table Group, Inc., a consulting firm.

2. Technical consultant for legal counsel in patent suit Dark Horse Trading Company versus Sega Game Works concerning Pellegrini US patent number 4,575,622, Aug, 2000.

3. Expert witness for WMS's legal counsel on WMS vs IGT slot machine software patent suit, Sept, 1997.

4. Technical consultant to Microsoft's legal counsel on STAC vs Microsoft Data Compression patent suit, 1994.

Patents

1. John H Reif, Peng Yin, Thomas H. LaBean, Geetha Shetty, Erik A. Schultes, Analyte Detection Using Autocatalytic Chain Reactions, US Patent Application 11/775,740, Filed July 10, 2007. Publication Date: April 2, 2009. [PDF] Assignee: Eagle Eye Research, Inc.

2. John H Reif, Thomas H. LaBean, Erik A. Schultes, Autonomous in Vitro Evolution, Assignee: Eagle Eye Research, Inc.

Consulting Positions

1. NASA Johnson Space Flight Center, consultant on Consolidated Space Operations Contract, Houston, Texas, July, 1997.

2. NASA ICASE Space Flight Center, Norfolk, Virginia, July, 1996.

3. NEC research center, Princeton New Jersey, July, 1995.

4. RTware, NC, real time software and algorithms, 1993.

5. Department of Mathematical Sciences, IBM Watson Research Institute. Yorktown Heights, NY, Summers of 1983 and 1984.

6. GTE Laboratories, VLSI Design Project. Waltham, MA, Spring and Summer 1985.

7. Thinking Machines, Inc. Connection Machine Project. Cambridge, MA, 1985-1988.

8. Barakat Associates, Air Force contract: Optical Devices and Optical Computing. Lexington, MA, Fall 1985.

9. MRJ, Park and Elmer, Design of Parallel Algorithms for the Connection Machine. Fairfax, VA, 1985-1988

10.NASA Goddard Space Flight Center, Space Data and Computing Division, Massive Parallel Processing (MPP) Project. Greenbelt, MD, 1985-1988.

11.Microelectronic Center for North Carolina (MCNC), 2nd Generation Massively Parallel Processor Project, (PI of $300,000 NASA contract supporting this work), initiator of and co-architect (with Ed Davis) of BLITZEN 128 processor chip, 1986-1988. (see System Projects #2)

Journals and Book Series Advisory Boards

1. Chair of Duke University ‘s Executive Committee for Nanoscience (GPNANO), 2005-2009

2. Editor, Special Issue on STOC2003, (devoted to selected papers from the 34th Annual ACM Symposium on Theory of Computing (STOC2002), Journal of Computer and System Sciences (JCSS), Volume 67. No. 2, Sept. 2003, pp. 211-471. [PDF]

3. Member of Editorial Board of the Journal of Computational and Theoretical Nanoscience (CTN), American Scientific Publishers, USA, 2004-2006.

4. Member of Editorial Board of the Journal of Experimental Nanoscience, Taylor and Francis, USA(starting January 1, 2006).

5. Member of Advisory Board, Theory and Practice of Object Systems, Wiley, New York, 2000-2007.

6. Member of Advisory Board, Series on Natural Computing, Springer-Verlag.
7. Member of Advisory Board, Springer Series in Computer Science and Computer Security for Higher Education Press of Ministry of Education of China.

Conference Organizations

1. Member of Program Committee, Aegean Workshop on Computing, Corfu, Greece, June 1986.

2. Member of Program Committee, 20th Symposium on Theory of Computer Science, May 1988.

3. Member of Program Committee, 3rd International Conference on Supercomputing, Boston, Massachusetts, May 1988.

4. Chairman of Program Committee, Aegean Workshop on Computing, Corfu, Greece, June 1988.

5. Member of Program Committee, 2nd Symposium on Frontiers of Massively Parallel Computing, Fairfax, Virginia, October 1988.

6. Member of Program Committee, 22nd Symposium on Theory of Computer Science, May 1990.

7. Member of Program Committee, 4th Symposium on Frontiers of Massively Parallel Computing, Fairfax, Virginia, October 1990.

8. Program co-Chairman, First IEEE Conference on Data Compression, Snowbird, Utah, April 1991. (Sponsored by IEEE Computer Society)

9. Member of Program Committee, 32nd IEEE Symposium on Foundations of Computer Science, October 1991. (Sponsored by IEEE Computer Society)

10. Member of Program Committee, Sixth International Parallel Processing Symposium, Beverly Hills, California, March 23-26, 1992. (Sponsored by IEEE Computer Society)

11. Member of Program Committee, Second IEEE Conference on Data Compression, Snowbird, Utah, March 1992. (Sponsored by IEEE Computer Society)

13. Member of Program Committee, Third IEEE Conference on Data Compression, Snowbird, Utah, March 1993. (Sponsored by IEEE Computer Society)

14. Member of Program Committee, Fourth IEEE Conference on Data Compression, Snowbird, Utah, March 1994. (Sponsored by IEEE Computer Society)

15. Member of Advisory Committee, Workshop of Parallel Algorithms (WOPA),1994.

16. Member of Program Committee, Second International Conference on Massively Parallel Processing Using Optical Interconnects (MPPOI1995)

19. Member of Program Committee, IEEE Data Compression Conference(DCC95)

20. Member of Program Committee, 1st Annual Meeting on DNA Based Computers(1995)

21. Member of Program Committee, Workshop On Randomized Parallel Computing, 10th International Parallel Processing Symposium (IPPS '96).

22. Member of Program Committee, 8th Annual ACM Symposium on Parallel Algorithms and Architectures(SPAA96)

23. Member of Program Committee, IEEE Data Compression Conference(DCC96)

24. Member of Program Committee, 2nd Annual Meeting on DNA Based Computers(1996)

25. Member of Program Committee, 3rd annual IEEE Conference on Massively Parallel Processing Architectures using Optical Interconnections (MPPOI'96)

26. Member of Program Committee, IEEE Data Compression Conference(DCC97).

27. Member of Program Committee, 3rd Annual Meeting on DNA Based Computers(1997).

28. Member of Program Committee, Workshop On Randomized Parallel Computing, 11th International Parallel Processing Symposium (IPPS '97).

29. Member of Program Committee, DIMACS Workshop on "Randomization Methods in Algorithm Design", Dec. 12-14, 1997, Princeton University. Probability.

30. Member of Program Committee, 4th International Symposium on Solving Irregularly Structured Problems in Parallel (IRREGULAR'97) University of Paderborn, Germany, 11-13 June 1997.

31. Member of Program Committee for the Algorithms and Applications track of 26th International Conference on Parallel Processing (ICPP97) August 11-15, Indian Lakes Resort in Bloomingdale, IL.

32. Member of Program Committee for the IEEE International Conference On Robotics And Automation, 1997.

33. Member of Organizing Committee, 4rth Annual Meeting on DNA Based Computing (1998).

34. Member of Program Committee, vIEEE Data Compression Conference(DCC98), Snowbird, Utah, 1998.

35. Member of Advisory Committee, Workshop on Parallel Algorithms (WOPA), 1998.

36. Member of Advisory Committee, 1999 Workshop on Algorithms and Data Structures (WADS'99) August 12-14, 1999 Vancouver, British Columbia, Canada.

37. Program Chair, Workshop in Biomolecular Computation: Its Potential and Applications, NSF, Arlington VI, Oct 1, 1999.

38. Member of Program Committee, IEEE Data Compression Conference(DCC99), Snowbird, Utah, 1999.

39. Member of Program Committee, Workshop on Algorithms and Data Structures (WADS1999).

40. Co-Organizer of East Coast Computer Algebra Day(ECCAD'99), NC State, Raleigh, NC, April 24, 1999.

41. Member of Program Committee, Workshop on Algorithmic Foundations of Robotics (WAFR2000).

42. Member of Executive Committee, DNA Based Computers, 2000.

43. Team Leader (with M. Morf) for DNA/Biological SRC meeting ADT Novel Technologies for Information Processing:, San Jose CA, (March 26, 2000).

43. Member of Program Committee, Seventh DNA Based Computers, June 2001.

43. Panel Moderator: Critical Assessment of Techniques for Microarray Data Analysis (CAMDA2000 Conference), Duke University, Durham, NC, 2001

44. Member of Organizing Committee, Special session on Molecular Evolutionary Computing, 2001 Congress on Evolutionary Computation (CEC2001) Seoul, Korea during May 27-30, 2001. at CEC2001.

45. Member of Program Committee, Seventh International Meeting on DNA Based Computers (DNA7), Tampa, FL, June 11-13, 2001.

46. Chairman of Program Committee, Symposium on Theory of Computing (STOC2002), May, 2002.

47. Member of Program Committee, track on Biomolecular computing and quantum computing at Genetic & Evolutionary Computation Conference Conference (GECCO 03), Chicago, IL, July 2002.

48. co-Chairman of Program Committee, Ninth International Symposium on DNA Based Computers (DNA9), Madison, Wisconsin, June, 2003.

49. Program Chairman of the First Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices(FNANO04), Snowbird, Utah, (April 21-23, 2004).

50. Member of the Godel Prize Committee, ACM SIGACT, 2004-2005.

51. Member of Program Committee, Fourth IEEE International Workshop on High Performance Computational Biology (HiCOMB 2005).

52. Program Chairman of the Second Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices(FNANO05), Snowbird, Utah, (April 24-28, 2005).

53. Program coChairman of the NSF Workshop: Emerging Opportunities of Nanoscience to Energy Conversion and Storage, Arlington VI, November 21-22, 2005.

54. Member of the Godel Prize Committee, ACM SIGACT, 2005-2008.

55. Member of Program Committee, 18th ACM Symposium on Parallelism in Algorithms and Architectures(SPAA06), Cambridge, MA, July 30 - August 2, 2006.

56. Program Chairman of the Third Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices(FNANO06), Snowbird, Utah, (April 23-27, 2006).

57. Member of the Program Committee (for Programmable self assembly) of 2006 Robotics Science and Systems Conference (RSS 2006), University of Pennsylvania, Philadelphia, PA, August 16th-19th, 2006.

58. Chair of the Godel Prize Committee, ACM SIGACT, 2006-2007.

59. Program Chairman of the Fourth Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices(FNANO07), Snowbird, Utah, (April 18-21, 2007).

60. Member of the DNA Computing Steering Committee, 2001-current.

61. Member of the ISNSCE Council, 2006-current.

62. Chair of ISNSCE Scientific Advisory Council, 2006-current.

63. General Chairman of the Fifth Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices(FNANO07), Snowbird, Utah, (April 25-28, 2008).

64. Member of the Steering committee of 1st International Conference on Bioinformatics and Computational Biology (BICoB), New Orleans, Louisiana.

65. General Chairman of the Sixth Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices(FNANO07), Snowbird, Utah, (April 20-24, 2009).

66. Member of Steering committee of International Conference on Bioinformatics and Computational Biology (BICoB), , March 25-27, 2009, New Orleans, Louisiana USA.

67. Member of Program Committee of DNA16, (June 2010).

68. General Chairman of the Seventh Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices(FNANO07), Snowbird, Utah, (April 27-30, 2010).

Recent Invited Talks

Biomolecular Computation by Local Assembly, University of Delaware, Mathematics Dept, April 19, 1997

Biomolecular Computation by Local Assembly, U Pennsylvania, April 18, 1997

Biomolecular Computation, Ultrascale Meeting, DARPA, Estes Park, CO, Oct 14, 1997.

Biomolecular Computation (Distinguished Lecture Series), Department of Computer Science, Rice University, April 30, 1997

Approximate Complex Polynomial Evaluation, Department of Computer Science, U. of Houston, May 1, 1997

Randomized parallel algorithms in computational geometry, October 10, 1997, School and Workshop on Randomized Algorithms in Sequential, Parallel, and Distributed Computing(RALCOM 97),Santorini Island, Greece.

Randomized parallel algorithms for routing and sorting October 11, 1997, Workshop on Randomized Algorithms in Sequential, Parallel, and Distributed Computing(RALCOM 97), Santorini Island, Greece.

Biomolecular Computation, CS Dept, Brandeis University, Nov 22, 1997.

Robust, Adaptive and Dynamic Robotic Motion Planning, 19 NSF Design and Manufactoring Grantees Conference, Monterrey, Mexico, Jan 1998.

Paradigms for Biomolecular Computation, First International Conference on Unconventional Models of Computation, Auckland, New Zealand, January 1998. in Unconventional Models of Computation, edited by C.S. Calude, J. Casti, and M.J. Dinneen, Springer Publishers, January 1998, pp. 72-93.

Microflow Bio-Molecular Computation, 4th DIMACS Workshop on DNA Based Computers, University of Pennsylvania, June, 1998.

Nano-Robotics Motion Planning and Its Applications in Nanotechnology and Biomolecular Computing, NSF Design and Manufacturing Grantees Conference, Longbeach, CA, Jan 5-8, 1999.

Quantum Information Processing: Compression, Coding, and Related Computations, Plenary Talk, IEEE Data Compression Conference (DCC'99) Snowbird, Utah, March 29 - 31, 1999.

Experimental Progress in Computation by Self-Assembly of DNA Tilings, 5th DIMACS Workshop on DNA Based Computers, MIT, June 14, 1999.

DNA-based Cryptography, 5th DIMACS Workshop on DNA Based Computers, MIT, June 15, 1999.

Molectronics Software Architecture, DARPA Molelectronics Meeting, Ashburn, VI, July8-9, 1999.

DNA Cryptosystems, Workshop in Biomolecular Computation: Its Potential and Applications, NSF, Arlington VI, Oct 1, 1999, (abstract).

Collaborative Biomolecular Computation Projects in Europe, Japan, & the US, Workshop in Biomolecular Computation: Its Potential and Applications, NSF, Arlington VI, Oct 1, 1999, (abstract).

Nonparametric Multiscale Multimodal Model for Detection/Recognition, Multi-Modality Image Fusion Conference, Rochester, NY, Oct 7, 1999.

Software Architecture for a Molecular Computer, DARPA, Arlington VI, Nov 30, 1999.

Molectronics Software Architecture, Center Nanoscale Science and Technology, Rice University, Dec 3, 1999.

DNA Cryptosystems, Invited Talk, National Security Agency(NSA), Fort Meade, Maryland, Dec 13, 1999.

Associative Search in DNA Databases, Invited Talk, National Reconnaissance Office(NRO), Chantilly, VA, Dec 14, 1999.

Software Design for Molectronics, DARPA Molectronics Meeting, Arlington, VI, (Feb 26,2000).

An Efficient Approximation Algorithm for Weighted Region Optimal Path Problem, Workshop on Foundations of Robotics (WFR2000), Dartmouth, NH, (March 17, 2000).

Self-Assembled DNA Nanostructures, ADT Novel Technologies for Information: DNA/Biological SRC meeting, San Jose CA, (March 26, 2000).

Self-Assembled DNA Nanostructures, NSF workshop on nano-scale molecular based electronics, Arlington, VI, (May 18, 2000).

Computationally Inspired Biotechnologies: Improved DNA Synthesis and Associative Search Using Error-Correcting Codes and Vector-Quantization, Invited Talk, Sixth International Meeting on DNA Based Computers (DNA6), Leiden, The Netherlands, (June 14, 2000)

Challenges and Applications for Self-Assembled DNA Nanostructures, Plenary Talk, Sixth International Meeting on DNA Based Computers (DNA6), Leiden, The Netherlands, (June 16, 2000)

Algorithmic self-assembly of DNA Tilings, City University of Hong Kong, Kowloon, Hong Kong, Oct 2, 2000.

Improved DNA Synthesis and Associative Search Using Error-Correcting Codes and Vector-Quantization, City University of Hong Kong, Kowloon, Hong Kong, Oct 3, 2000.

On the Impossibility of Interaction-Free Quantum Sensing for Small I/O Bandwidth, City University of Hong Kong, Kowloon, Hong Kong, Oct 4, 2000.

A Biomolecular System for Ultra-Scale Associative Search, Invited Talk, National Reconnaissance Office(NRO), Chantilly, VA, November, 2000.

A Biomolecular System for Ultra-Scale Associative Search, Theory Seminar, CS Dept, Duke University, Durham, NC, November 16, 2000.

Experimental Demonstrations of Ultra-Scale Molecular Data Storage & Retrieval, Computation and Assembly, Information Science and Technology Colloquium Series Invited Talk, NASA Goddard, Maryland, Jan 17, 2001.

Programmable Assembly at the Molecular Scale: Self-Assembly of DNA Lattices, Plenary Talk, 2001 IEEE International Conference on Robotics and Automation (ICRA2001), Seoul, Korea, May 26, 2001

Molecular Computing via Programmed Self-Assembly of Patterned Molecules, Plenary Talk, 2001 Congress on Evolutionary Computation (CEC2001), Seoul, Korea, May 28, 2001

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.

Molecular Database Systems for Storage, Processing & Retrieval of Genetic Information & Material, Invited Talk, MiniSymposium "On Interfaces among Information Technology, sensing sciences, and Biological Systems", organized by Jagdish Chandra and Srikanta Kumar, SIAM Annual Meeting, San Diego, California, July 9-13, 2001

Movement Planning in the Presence of Flows, Workshop on Algorithms and Data Structures (WADS2001), Brown University, Providence, RI, August 8-10, (2001).

Computations & patterned structures via DNA self-assembly, Invited talk, Max Planck Institute for the Physics of Complex Systems, Dresden, Germany, August 20-24,2001.

DNA in NanoScience, Invited talk, Department of Computer Science Seminar Series,, Duke University, Durham, NC, October 22, 2001

DNA Computation by Self-Assembly of DNA Nano-Scale Structures, Symposium on New Approaches toward Computing, Plenary Talk, National Academy of Arts and Sciences, Brussels, Belguim, November 9, 2001

Programmable DNA Lattices: Design, Synthesis and Applications, Invited Talk, Joint DARPA/NSF BioComp PI Meeting, Monterey Bay, CA. November, 27 - 30, 2001.

Self-Assembly of DNA Nano-Scale Structures for Computation, Invited Talk, Joint DARPA/NSF BioComp PI Meeting, Monterey Bay, CA. November, 27 - 30, 2001.

Self-Assembly of DNA Nano-Scale Structures, Invited Talk, DARPA ITO BioComp PI Meeting, Washington, DC, May 22-24, 2002.

DARPA Supplemental Project Overview, Invited Talk, Central Intelligence Agency(CIA), McLean, VI, Feb 12, 2002.

DNA Database Project Final Report Talk, National Reconnaissance Office(NRO), Chantilly, VA, Feb 12, 2002.

The Design of Autonomous DNA Nanomechanical Devices: Walking and Rolling DNA, The 8th International Meeting on DNA Based Computers (DNA 8), Sapporo, Japan, June 10-13, 2002.

Molecular Assembly and Computation: From Theory to Experimental Demonstrations, Plenary Talk, 29th International Colloquium on Automata, Languages, and Programming(ICALP), Málaga, Spain (July 8, 2002).

Programmable Molecular Self-Assembly: Theory and Experimental Demonstrations, invited talk, Alternative Computing Workshop, Mathematics in Nanoscale Science and Engineering, UCLA, September 30, 2002.

Programmable Molecular Self-Assembly: Theory and Experimental Demonstrations, distinguished lecture, Computer Science Department, John Hopkins University, Baltimore, Maryland, October 3, 2002.

DARPA Supplemental Project Overview Talk & Demonstration, MITRE Corporation, McLean, VI, October 4, 2002

Programmable DNA Lattices: Design, Synthesis and Applications, Invited Talk, Department of Computer Science, Boston University, Boston, MA, December 2, 2002.

Patterned Molecular Self-Assembly, Invited Talk, Joint DARPA/NSF BioComp PI Meeting, San Deigo, CA. December 7, 2002.

DARPA Supplemental Project Overview Talk & Demonstration, MITRE Corporation, McLean, VI, April 14, 2003

DNA Nanostructures: Patterning and Computation, Duke Nanostructure Workshop, Duke University, Durham, NC, May 5, 2003

Achieving Patterned Molecular Self-Assembly, Invited Talk, DARPA BioComp PI Meeting, Fort Lauderdale, Florida, May 15, 2003.

Directed Nucleation Assembly of Barcode Patterned DNA Lattices, DNA9 Conference, Madison, Wisconsin, June 2, 2003

Programmable DNA Lattices: Design, Synthesis and Applications, Keynote Talk, 5th Conference on Computational Biology and Genome Informatics (CBGI), 7th Joint Conference on Information Sciences (JCIS 2003), September 26-30,2003. Cary, NC, USA.

Compact Error-Resilient Computational DNA Tiling Assemblies, Tenth International Meeting on DNA Based Computers (DNA10), Milano, Italy, June 7-10, 2004.

Designs for Autonomous Unidirectional Walking DNA Devices, Tenth International Meeting on DNA Based Computers (DNA10), Milano, Italy, June 7-10, 2004.

Design of an Autonomous DNA Nanomechanical Device Capable of Universal Computation and Universal Translational Motion, Poster Presentation, Tenth International Meeting on DNA Based Computers (DNA10), Milano, Italy, June 7-10, 2004.

TileSoft: Sequence Optimization Software For Designing DNA Secondary Structures, Poster Presentation, Tenth International Meeting on DNA Based Computers (DNA10), Milano, Italy, June 7-10, 2004.

DNA-Based Nano-Engineering: DNA and its Enzymes as the Engines of Creation at the Molecular Scale, Plenary Invited Talk, Tenth International Meeting on DNA Based Computers (DNA10), Milano, Italy, June 7-10, 2004.

Design, Simulation, and Experimental Demonstration of Self-Assembled DNA Nanostructures and DNA Motors, Invited Talk, Computational Modeling and Simulation of Materials (CIMTEC) Conference, Acireale, Sicily, Italy, May 29-June 4, 2004.

Molecular Computations Using Self-Assembled DNA Nanostructures and Autonomous Motors, Invited Talk, Bio-inspired Computing Track, Unconventional Programming Paradigms (UPP), Mont Saint-Michel, France, September 15–17, 2004.

Self-Assembled DNA Nanostructures for Molecular Scale Patterning, Computation and Motors, Invited Talk, Korean Society for Bioinformatics Conference, Seoul, South Korea, November 5, 2004.

Self-Assembled DNA Nanostructures for Molecular Scale Patterning, Computation and Motors, Invited Talk, Nano System Institute (NSI_NCRC), Seoul National University, Seoul, South Korea, November 8, 2004.

Self-Assembled DNA Nanostructures for Molecular Scale Patterning, Computation and Motors, Invited Talk, Biomedical MEMS Laboratory, Korea Institute of Science and Technology (KIST), Seoul, South Korea, November 8, 2004.

Self-Assembled DNA Nanostructures for Molecular Scale Patterning, Computation and Motors, Invited Talk, Division of Nano Science, Ewha Woman’s University, Seoul, South Korea, November 9, 2004.

Self-Assembled DNA Nanostructures for Molecular Scale Patterning, Computation and Motors, Invited Talk, Department of BioSystems, Korean Advanced Institute of Science and Technology (KAIST), Taejon, South Korea, November 9, 2004.

Self-Assembled DNA Nanostructures for Molecular Scale Patterning, Computation and Motors, Invited Talk, Department of Materials Science and Engineering, Massachusetts Institute of Technology (MIT), Cambridge, MA, December 6, 2004.

Self-Assembled DNA Nanostructures for Molecular Scale Patterning, Computation and Motors, Invited Talk, Department of Chemistry, Tufts University, Medford, MA, December 7, 2004.

Self-Assembled DNA Nanostructures for Molecular Scale Patterning, Computation and Motors, Invited Talk, Workshop on Engineering a DNA World, Center for Biological Circuit Design, California Institute of Technology (Caltech), Pasadena, CA, January 6-8, 2005.

Self-Assembled DNA Nanostructures for Molecular Scale Patterning, Computation and Motors, Invited Talk, Departments of EE and Material Science, Seattle, WA, February 15, 2005.

Self-Assembled DNA Nanostructures for Molecular Scale Patterning, Computation and Motors, Invited Talk, Frontiers 2005, Duke University, Durham, NC, May 4, 2005.

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, June, 2005.

Peng Yin, Andrew J. Turberfield, John H. Reif, Design of Autonomous DNA Cellular Automata, Eleventh International Meeting on DNA Based Computers (DNA11), London, Ontario, June, 2005.

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, June, 2005.

Self-Assembled DNA Nanostructures for Molecular Scale Patterning, Computation and Transport, Invited Talk, New York Academy of Science, New York, NY, Oct 11, 2005.

Design and Simulation of Self-Repairing DNA Lattices, 12th International Meeting on DNA Computing (DNA 12), Seoul, Korea, June 5-9, 2006.

On Constructing Tile-less DNA Ribbons and Tubes, 12th International Meeting on DNA Computing (DNA 12), Seoul, Korea, June 5-9, 2006.

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.

DNA Modeller: Modeling DNA based Molecular Systems, Poster Abstract, 12th International Meeting on DNA Computing (DNA 12), Seoul, Korea, June 5-9, 2006. (Poster Abstract).

Self-Assembled DNA Nanostructures for Molecular Scale Patterning, Computation and Transport, Invited Talk, 14th Workshop on Logic, Language, Information and Computation (WoLLIC'2007), Rio de Janeiro, Brazil, July 2-5, 2007.

DNA Self-assembly and Autonoumous R Molecular Robots. Invited Talk, presented at the Conference on Morphological Computation, Venice, Italy, March 26-28, 2007.

Autonomous Programmable Biomolecular Devices Using Self-Assembled DNA Nanostructures, invited talk, Fourteenth Workshop on Logic, Language, Information and Computation (WoLLIC'2007), Rio de Janeiro, Brazil, July 2-5, 2007.

Autonomous Programmable DNA Nanorobotic Devices Using DNAzymes, 13th International Meeting on DNA Computing (DNA 13), Memphis, Tennessee, June 4-8, 2007.

Activatable Tiles for Compact Error-Resilient Directional Assembly. 13th International Meeting on DNA Computing (DNA 13), Memphis, Tennessee, June 4-8, 2007.

Autonomous Programmable Biomolecular Devices Using Self-Assembled DNA Nanostructures, invited talk, Workshop on Algorithmic Bioprocesses, Lorentz Center, Leiden University, Leiden, Netherlands, Dec 3-7, 2007.

Autonomous Programmable Biomolecular Devices Using Self-Assembled DNA Nanostructures, invited talk, joint talk, University of Vancouver & Simon-Fraser University, Jan 30, 2008.

Isothermal Reactivating Whiplash PCR for Locally Programmable Molecular Computation, Fourteenth International Meeting on DNA Based Computers (DNA14), Prague, Czech Republic (June, 2008).

Programmable DNA Nanodevices, NSF EMT 2008 Workshop, Princeton, JN, July 24-25, 2008.

DNA nanoassembly and DNA Nanodevices: Challenges, Applications and Research Progress, DNA-based nanotechnology: Construction, mechanics, and electronics, International Workshop, Dresden, Germany, (May 11 - 15, 2009).

DNA nanoassembly and DNA Nanodevices: Challenges, Applications and Research Progress, Future and Emerging Technologies (FET) seminar, European Commission, Brussels, Belgium, (May 20, 2009).

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

The Tile Complexity of Linear Assemblies, 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), July 5 - 12, 2009, Rhodes, Greece.

DNA nanoassembly and DNA Nanodevices: Challenges, Applications and Research Progress, Computer Technology Institute, University of Patras, Patras, Greece (July 19, 2009).

Books

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

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

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

4. 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), 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. 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.

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]

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 n^1+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(log² 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: pp. 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 Jörg-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, 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), Málaga, 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ö Högskola, 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, Abstract, Preliminary Proceedings, Ninth International Meeting on DNA Based Computers (DNA9), Madison, Wisconsin, (June 2-4, 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ö Högskola, 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 Banâtre, 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, Springer New York (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-Reconfigurable 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)