Date: Thu, 07 Nov 1996 19:06:55 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Tue, 03 Oct 1995 22:00:45 GMT Content-length: 2640 Home Page of Anne Condon

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
Ph.D., University of Washington, 1987
Interests: Complexity theory, interactive proof systems, randomized complexity classes, theory of parallel computation


Research Summary

I am interested in models of computation, such as interactive proof systems, which combine nondeterminism and randomness. Such models have recently proven surprisingly useful in solving classic problems in complexity theory. For example, although the theory of NP-completeness has long been used to identify hard computational problems, there has not been much progress in understanding which hard problems have solutions that are easy to approximate. Recent results on interactive proof systems have resulted in novel models of NP, which in turn can be used to prove non-approximability results for several NP-hard problems. In our work we are developing both positive and negative results on the approximability of hard combinatorial problems which arise in game theory, graph theory and automata theory.

I am also interested in design and analysis of parallel algorithms. I am currently working on development of parallel algorithms for sorting and for graph problems, such as minimum spanning tree. The goal is to develop algorithms that work well on `practical' parallel models, where communication and synchronization costs can be expensive.

Sample Recent Publications

Interactive proof systems with polynomially bounded strategies (with R. Ladner), Journal of Computer and System Sciences, vol. 50, no. 3, 1995.

Finite state automata with nondeterministic and probabilistic states (with L. Hellerstein, S. Pottle, and A. Wigderson), Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, May 1994.

PSPACE is provable by two provers in one round (with J.-Y. Cai and R. Lipton), Journal of Computer and System Sciences, vol. 48, no. 1, February 1994.


This page was automatically created October 3, 1995.
Email pubs@cs.wisc.edu to report errors.