Associate Professor of Computer Sciences and MathematicsPh.D., Purdue University, 1981
Computer Sciences Department
University of Wisconsin
1210 W. Dayton St.
Madison, WI 53706-1685
telephone: (608) 262-1204
fax: (608) 262-9777
In the last twenty years a great deal of work has gone into studying the properties of sets that are decidable in deterministic and nondeterministic polynomial time. Despite this effort we still know very little about these classes. Recently in fact some computer scientists have questioned the adequacy of known proof techniques for resolving questions such as whether P = NP? My research investigates the structural properties of sets in these classes and explores in a formal way the types of proof techniques necessary to resolve problems concerning complexity classes.
My research interests in computational biology are primarily in the area of computational methods for genome sequencing. These included the development of dynamic data structures and algorithms for fragment assembly in large scale genome sequencing projects, and the development of specific algorithmic techniques for handling repetitive sequences. In addition my research has utilized graph theoretic methods for doing rapid homology detection in the analysis of anonymous sequences.
On sparse spanners of weighted graphs (with I. Althofer, G. Das, D. Dobkin, and Soares), Discrete and Computational Geometry, vol. 9, 1993.
Obtaining global similarity from local similarity (with J. Meidanis and P. Tiwari), in Proceedings of the Fourth Scandinavian Workshop on Algorithms, Springer-Verlag Lecture Notes in Computer Science, vol. 621, pp. 326-337, 1992.