Anne Condon

Associate Professor

Computer Sciences Department
University of Wisconsin
1210 W. Dayton St.
Madison, WI 53706-1685

telephone: (608) 262-1204
fax: (608) 262-9777
email: condon@cs.wisc.edu
http://www.cs.wisc.edu/~condon/

Ph.D., University of Washington, 1987
Interests: Complexity theory, approximability of NP-hard problems, randomized complexity classes, theory of parallel computation, DNA computing

Research Summary

My interests are in complexity theory and analysis of algorithms.

Currently, my work in these areas focuses on NP-hard problems, a class of problems that have no known efficient algorithms. NP-hard problems arise in many areas of scientific endeavor. I study mathematical techniques that can be used to identify which problems have good approximation algorithms and which do not. I am also working on analysis of efficient algorithms for graph partitioning and related problems on random inputs.

A recent interest is the area of DNA computing. A goal of this area is to store digital information in DNA molecules and to perform logical operations on that information, thereby "computing" with DNA. With Professors Rob Corn and Lloyd Smith of the UW-Madison Chemistry Department and Professor Max Lagally of the Materials Sciences Department, I am studying methods for performing DNA computation based on surface chemistry.

Sample Recent Publications

A surface-based approach to DNA computation (with L. Smith, R. Corn, M. Lagally, A. Frutos, Q. Liu, and A. Thiel), J. Computational Biology, vol. 5, Spring 1998.

Finite state automata with nondeterministic and probabilistic states (with L. Hellerstein, S. Pottle, and A. Wigderson), SIAM J. on Computing, vol. 27, June 1998.

On approximation algorithms for hierarchical MAX-SAT (with S. Agarwel), J. Algorithms, vol. 26, 1998.

This page was automatically created December 30, 1998.
Email pubs@cs.wisc.edu to report errors.