Ronitt Rubinfeld Assistant Professor ronitt@cs.cornell.edu http://www.cs.cornell.edu/home/ronitt/ronitt.html PhD UC Berkeley, 1990 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 introduced two new concepts that are 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 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 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:

(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 self-testers and self-correctors 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 real-valued 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 Activities

Science Fair Organizer: BOOM `98

Professional Activities

• Program Committee: FOCS 1997, COLT 1998

• Guest Co-editor: J. Computers and System Sciences, special issue on Symp. Theory of Computing (STOC) 1996

Awards

• NSF Career award (1996-2001)

• Alfred P. Sloan Research Fellow (1996-1998)

Lectures

• Understanding noisy data: the case of polynomials. Computer Science, Princeton Univ., Sept. 1997.

• ___. Computer Science, Rochester Univ., Sept. 1997.

• ___. Computer Science, Cornell, Sept. 1997.

• Spot checkers. Computer Science, Cornell, Feb. 1998.

• ___. Computer Science, Toronto, May 1998.

Publications

• Spot-checkers. STOC '98 (with F. Ergun, S. Kannan, S.R. Kumar and M. Vishwanathan).

• Learning distributions generated by random walks. COLT '97 (with F. Ergun and S.R. Kumar).