John H. Reif
CS Department Image
A. Hollis Edens Professor of Computer Science
Faculty Group: Algorithms
Email reif at
Office D223 LSRC
Phone (919) 660-6568
Web page


Ph.D., Harvard University, 1977
B.S., Tufts University, 1973

Honors & Awards

Fellow, American Association for the Advancement of Science, 2003; Fellow, Association for Computing Machinery (ACM), 1997; Fellow, Institute of Electrical and Electronics Engineers (IEEE), 1993; Fellow, Institute of Combinatorics and its Applications, 1991.


  • Molecular Computation (DNA nanostructure self-assembly, DNA computation, molecular robotics).
  • Algorithms (parallel algorithms, randomized algorithms, graph algorithms, algebraic algorithms, robot motion planning algorithms, data compression algorithms).
  • Complexity Theory (complexity of robot motion planning and of games of incomplete knowledge).
  • Optics (optical computation and solar concentrators).
  • Quantum Computation (quantum sensing and compression).
  • Research Initiative: Biological Computing & Nanotechnologies

    Selected Publications

    • Harish Chandran, Nikhil Gopalkrishnan, and John Reif, "The Tile Complexity of Approximate Squares and Lower Bounds for Arbitrary Shapes," Algorithmica, accepted and to appear (2012).
    • Harish Chandran, Nikhil Gopalkrishnan, Bernard Yurke, John Reif, "Meta-DNA: Synthetic Biology via DNA Nanostructures and Hybridization Reactions," Journal of the Royal Society Interface, accepted and to appear (2012).
    • John H. Reif and Sudheer Sahu, "Autonomous Programmable DNA Nanorobotic Devices Using DNAzymes," Special Journal Issue on Self-Assembly, Theoretical Computer Science (TCS), Vol 410, Issue 15, pp. 1428-1439 (April 2009).
    • Sudheer Sahu, Thom H. LaBean and John H. Reif, "A DNA Nanotransport Device Powered by Polymerase ϕ29," Nano Letters, 2008, 8 (11), pp 38703878, (October, 2008) (DOI: 10.1021/nl802294d.)

    • Peng Yin, Rizal F. Hariadi, Sudheer Sahu, Harry M.T.Choi, Sung HaPark, 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.)

    Extended List of Publications

    Publications by John H. Reif