Anne Condon
Professor & MDS Co-Director
Academic Information
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).
Interests
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.
Selected Publications
A. Condon and R. M. Karp, "Algorithms for Graph Partitioning on the Planted Bisection Model", J. Random Structures and Algorithms, 18, 116-140, 2001.
Q. Liu, A. G. Frutos, L. Wang, A. Condon, R. M. Corn, and L. M. Smith, "DNA Computations on Surfaces", Nature, Vol. 403 pages 175-179, 2000.
O. Madani, A. Condon, and S. Hanks, "On the Undecidability of Probabilistic Planning and Infinite-Horizon Partially Observable Markov Decision Process Problems", Sixteenth National Conference on Artificial Intelligence (AAAI'99), July 1999.
A. Condon, L. Hellerstein, S. Pottle, and A. Wigderson, "Finite State Automata with Nondeterministic and Probabilistic States", SIAM Journal on Computing, Vol. 27, No. 3, pages 739-762, June 1998.