Computer Science - Duke University

John Reif

A. Hollis Edens Professor of Computer Science

Faculty Group: Algorithms

Email	reif at cs.duke.edu
Office	D223 LSRC
Phone	(919) 660-6568
Fax	(919) 660-6519
Web page	http://www.cs.duke.edu/~reif

Education

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.

Research

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 3870–3878, (October, 2008) (DOI: 10.1021/nl802294d.)
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.)

Extended List of Publications

Publications by John Reif