Anne Condon

Professor & MDS Co-Director

Office Phone #
On Sabbatical Jan 1 - June 1 2021

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


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.

Research Interests


Research Groups

Algorithms Lab

Latest Courses

2020 Summer

CPSC 320 - Intermediate Algorithm Design and Analysis

2019 Winter

CPSC 506 - Complexity of Computation
CPSC 320 - Intermediate Algorithm Design and Analysis

2018 Winter

CPSC 320 - Intermediate Algorithm Design and Analysis
CPSC 320 - Intermediate Algorithm Design and Analysis

2017 Winter

CPSC 500 - Fundamentals of Algorithm Design and Analysis

2016 Winter

CPSC 100 - Computational Thinking
CPSC 506 - Complexity of Computation