Anne Condon

Email: condon [at] cs [dot] ubc [dot] ca
Office: ICCS X551
Phone: 604-822-8175

Curriculum Vitae

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).


theoretical computer science
analysis of algorithms
dna computing
verification of finite state protocols
computational complexity theory


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.

a place of mind, The University of British Columbia


ICICS/CS Building 201-2366 Main Mall
Vancouver, B.C. V6T 1Z4 Canada
Tel: 604-822-3061 | Fax: 604-822-5485
Undergrad program:
Graduate program:

Emergency Procedures | Accessibility | Contact UBC | © Copyright The University of British Columbia