In 1994, Adleman introduced a novel and well publicized model of computation using DNA molecules. The model is basically founded on three primitives, Extract, Merge and Detect. Each of these primitives operates in parallel on a test tube; i.e., a large set of DNA strands, each of which encodes a sequence of bits. In particular, the Extract primitive splits a test tube into two test tubes according to the value of a particular bit $x$. The Merge primitive combines the contents of two test tubes, and the Detect primitive determines whether a test tube is empty.

The first half of this talk is a brief survey of existing results in the area of the DNA computers introduced by Adleman, and the second half describes recent results of Richard Karp, Claire Kenyon and myself that explore the issue of making DNA computers error resilient. Our work also introduces a new lower bound technique which may apply for other problems which involve massive parallelism.

Orli Waarts received her Ph.D. from Stanford University in 1992. She is currently a research fellow in the Computer Science Department at the University of California at Berkeley, sponsored by an NSF Mathematical Sciences postdoctoral fellowship. Her research interests include algorithms and lower bounds, particularly in the fields of on-line algorithms, computational biology, distributed computation, and networks.

This Forum is OPEN to the public.
Host: Marti Hearst, (415) 812-4742, hearst@parc.xerox.com