Associate ProfessorPh.D., University of Washington, 1987
Computer Sciences Department
University of Wisconsin
1210 W. Dayton St.
Madison, WI 53706-1685
telephone: (608) 262-1204
fax: (608) 262-9777
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.
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.