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 at cs.wisc.edu

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 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 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.' In practice one usually finds a witness by direct search among the small primes. This leads to the following natural question. How large is the least witness, as a function of the number tested? In recent work, we have given an accurate heuristic model, based on probabilistic assumptions, that allows this, and similar questions, to be answered.

Some Recent Publications

Algorithmic Number Theory (Volume I: Efficient Algorithms) (with J. Shallit), MIT Press, 1996. For info click on ANT-1.

DNA models and algorithms for NP-complete problems (with A. Condon, E. Glaser, S. Tanguay), Journal of Computer and System Sciences 57, 172-186, 1998.

Threshold data structures and coding theory (with M. Kiwi) Theoretical Computer Science 235, 3-23, 2000. Special issue dedicated to Manuel Blum.

One-dimensional quantum walks (with A. Ambianis, A. Nayak, A. Vishwanath, and J. Watrous) Proc. 33rd ACM Symposium on Theory of Computing, pp. 37-49, 2001.

On testing for zero polynomials by a set of points with bounded precision (with J.-Y. Cai), Proc. 2001 Conference on Combinatorics and Computing (COCOON), to appear.

Curriculum Vitae

Mea Culpa

This page created July 30, 1996.