Since the early 1970's, the theory of NP-completeness has provided a powerful way to classify which combinatorial problems are "easy" and which are "intractable". A major achievement of computational complexity theory in the 1990's has been to identify which intractable problems have solutions that can be approximated efficiently and which don't - resolving open questions that had remained open since the 1970's. Key to this achievement is the theory of interactive proof systems, which are computations that interleave both non-deterministic and random moves. In my research I study the power of such computations and implications for the computational complexity of combinatorial problems.

The field of biomolecular computation addresses the following questions: Can information storage and computations be performed at the molecular level, using DNA molecules? Can new nanostructures and materials be assembled in a programmable fashion from DNA? I study combinatorial and algorithmic problems that arise in the design of DNA strands that behave well in real DNA computing experiments.