Ronitt Rubinfeld

Ronitt Rubinfeld
Assistant Professor
ronitt@cs.cornell.edu
http://www.cs.cornell.edu/home/ronitt/Rubinfeld.html
Ph.D. University of California, 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 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. Our goal is to characterize the functions that have fast and simple checkers. We are investigating 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 have used such 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. 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 for the stability theory of functional equations.

Awards

Office of Naval Research Young Investigator Award (1993-1996)
1995 NSF Career Award
Alfred P. Sloan Research Fellow
College of Engineering Teaching Award

University Activities

On leave 1995-1996 at MIT

Professional Activities

Reviewer: SIAM Journal on Computation; Information and Computation; IPL; JACM; Algorithmica; Computational Complexity
Member, Program Committee: Symposium on Theory of Computing, May 22-24, 1996, Philadelphia, PA

Lectures

Short paths in expander graphs. Daghstuhl Workshop on Online Algorithms. Dagh-stuhl, Germany, June 23-28 1996.
On the robustness of functional equations. Dartmouth College, Hanover, NH, April, 1996.
____. DIMACS Workshop on Computational and Complexity Issues in Automated Verification, Rutgers, NJ, March 25-28, 1996.
Learning polynomials with queries: The highly noisy case. Workshop on Randomness Algorithms and Computation, Berkeley, CA, December, 1995.
____. 36th IEEE Conference on Foundations of Computer Science, Milwaukee, WI, November 1995.
On the robustness of functional equations. Workshop on Checking, Testing, and Security for Embedded Real-Time Software Systems, Hughes Aircraft Company, El Segundo, CA, November 10, 1995.
New directions and applications for learning finite automata. IBM Yorktown, August 1995.
____. Computer Science, University of California, Berkeley, CA, July, 1995.

Publications

Designing checkers for programs that run in parallel. Algorithmica 20, 3 (April 1996), 1-15.
Robust characterizations of polynomials and their applications to program testing. SIAM Journal of Computing 25, 2 (April 1996), 252-271 (with M. Sudan).
Learning polynomials with queries: The highly noisy case. Proceedings 36th IEEE Conference on Foundations of Computer Science. October 1995, 294-303 (with O. Goldreich and M. Sudan).
Efficient algorithms for learning to play repeated games against computationally bounded adversaries. Proceedings 36th IEEE Conference on Foundations of Computer Science. October, 1995, 332-341 (with Y. Freund, M. Kearns, Y. Mansour, D. Ron, and R. Schapire).
Exactly learning automata with small cover time. Proceedings 8th Annual ACM Workshop on Computational Learning Theory, 1995. 427-436 (with D. Ron).
On learning bounded-width branching programs. Proceedings 8th Annual ACM Workshop on Computational Learning Theory, 1995, 361-368 (with F. Ergun and S. Ravikumar).

Return to:

1995-1996 Annual Report Home Page
Departmental Home Page If you have questions or comments please contact: www@cs.cornell.edu. Last modified: 2 November 1996 by Denise Moore (denise@cs.cornell.edu).