My research interests include computational complexity and randomized computation. In particular, I have been working on 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 uses a program that is correct on most inputs to construct a new program that is correct on every input with high probability. Program checking is interesting for problems that are easy to specify but for which efficient programs may be complicated. Our goal is to characterize functions that have fast and simple checkers. We are conducting a number of investigations of checkers for problems in algebra, graph theory, and computational geometry. One fruitful line of research concerns self-testers and self-correctors based on properties satisfied by the function. For example, the function f(x)=x is uniquely specified by the properties that (1) for all x,y, f(x)+f(y)=f(x+y), (2) for all x, f(x)+1=f(x+1). We have used these properties to construct self-testers and self-correctors for several classes of functions, including the linear functions, many of the trigonometric functions, and low-degree polynomial functions.
In the area of computational learning theory, I have investigated algorithms for learning subclasses of deterministic finite state automata and probabilistic finite automata. Our algorithms have been modified by other researchers for use in systems for handwriting recognition and word-pronunciation understanding.
If you have questions or comments please contact: www@cs.cornell.edu.