Our work introduced two new concepts that are useful to the development of such checkers: A selftester determines whether a program is correct on most inputs, and a selfcorrector 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 the functions that have fast and simple checkers. We are conducting investigations of checkers for a variety of problems, including problems from algebra, graph theory, and computational geometry. One particularly fruitful line of research concerns selftesters and selfcorrectors based on properties satisfied by the function; for example, the function f(x) = x is uniquely specified by the properties: (1) for all x,y, f(x)+f(y) = f(x+y) (2) for all x, f(x)+1 = f(x+1) We used these properties to construct selftesters and selfcorrectors for several classes of functions, including linear functions, many trigonometric functions, and low degree polynomial functions. We have recently shown that our results apply to the setting of realvalued computation, where the output of the program is approximate instead of exact. Our results borrow techniques from and have implications to the stability theory of functional equations. University ActivitiesScience Fair Organizer: BOOM `98 Professional Activities
Awards
Lectures
Publications
