#
Eric Bach

Professor

Computer Sciences Department

University of Wisconsin

1210 W. Dayton St.

Madison, WI 53706-1685

telephone: (608) 262-1204

fax: (608) 262-9777

email:
bach@cs.wisc.edu

http://www.cs.wisc.edu/~bach/bach.html

*Ph.D., University of California, Berkeley, 1984*

*Interests:*
Theoretical computer science, computational number theory, algebraic
algorithms, complexity theory, cryptography, six-string automata

## Research Summary

I am primarily interested in how one uses computers to efficiently
solve algebraic and number-theoretic problems (example: how does
one tell if a 100-digit number is prime without examining all
possible factors?). These problems have intrinsic mathematical
interest, as well as applications to random number generation,
codes for reliable and secure information transmission, computer
algebra, and other areas. I am presently writing a book on this
subject, the first volume of which has just appeared.
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.

## Sample Recent Publications

Statistical evidence for small generating sets (with L. Huelsbergen),
*Mathematics of Computation*, 1993.
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.

This page was automatically created December 30, 1998.

Email pubs@cs.wisc.edu
to report errors.