My research interests include computational complexity and randomized computation. In particular, I have been working in the area of program correctness. The study of program checkers, self-testing programs and self-correcting programs is a new approach to ensuring the correctness of program results. The key idea is to allow one to use a program to compute a function without having to trust a priori that it works correctly. This is accomplished by having a checker determine whether the program gives the correct answer on a particular input. Our work has introduced two new concepts useful to the development of such checkers: a self-tester determines whether a program is correct on most inputs, and a self-corrector takes a program that is correct on most inputs and uses it to construct a new program that is correct on every input with high probability. Program checking is particularly interesting for problems that are easy to specify, but for which efficient programs may be very complicated. The goal of our research is to characterize which functions have fast and simple checkers. We are conducting a number of investigations of checkers for a variety of problems, including problems from algebra, graph theory and computational geometry.
Other recent work includes a new simple algorithm for factoring multivariate polynomials; algorithms for various new algebraic interpolation problems; and algorithms for learning deterministic finite state automaton.