Professor & MDS Co-Director
B.Sc., University College Cork (1982); Ph.D., U. Washington (1987); Assistant Professor, U. Wisconsin (1987-1994); Associate Professor, U. Wisconsin (1994-1999); Professor, U. Wisconsin and University of British Columbia (1999).
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.