ProfessorPh.D., University of California, Berkeley, 1984
Computer Sciences Department
University of Wisconsin
1210 W. Dayton St.
Madison, WI 53706-1685
telephone: (608) 262-1204
fax: (608) 262-9777
I am also interested in applying probability theory to the design and analysis of algorithms. For example, if a large number is composite, it can be proved so by a simple test that uses an auxiliary number, called a `witness.' Finding good estimates for the least witness is a long-standing open problem. Using large deviation theory, I designed accurate heuristic models for least witnesses, primitive roots, and other computationally interesting phenomena. In another application of probability theory, I used martingale theory to analyze the behavior of biochemical methods that may be used someday to solve NP-complete problems.
DNA models and algorithms for NP-complete problems (with A. Condon, E. Glaser and S. Tanguay), Proceedings of the 11th Annual Conference on Computational Complexity, 1995.
Algorithmic Number Theory (Volume I: Efficient Algorithms) (with J. Shallit), MIT Press, Cambridge, MA, August 1996.