Deborah A. Joseph

Associate Professor of Computer Sciences and Mathematics

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

telephone: (608) 262-1204
fax: (608) 262-9777
Ph.D., Purdue University, 1981
Interests: Structural and applied complexity theory, computational biology, computational geometry, mathematical logic

Research Summary

My research concerns two areas of theoretical computer science: 1) the study of structural properties of complexity classes, and 2) the design and analysis of algorithms for biological problems.

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.

Sample Recent Publications

Collapsing degrees in subexponential time (with R. Pruim and P. Young), Proceedings of the Ninth Structure in Complexity Theory Conference, 1994.

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.

This page was automatically created December 30, 1998.
Email to report errors.