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, selftesting programs, and
selfcorrecting 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 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. 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 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 have used such properties to construct selftesters and
selfcorrectors 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 realvalued 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 (19931996)
 1995 NSF Career Award
 Alfred P. Sloan Research Fellow
 College of Engineering Teaching Award
University Activities
 On leave 19951996 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
2224, 1996, Philadelphia, PA
Lectures
 Short paths in expander graphs. Daghstuhl Workshop on Online
Algorithms. Daghstuhl, Germany, June 2328 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 2528, 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 RealTime 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), 115.
 Robust characterizations of polynomials and their applications to
program testing. SIAM Journal of Computing 25, 2 (April 1996),
252271 (with M. Sudan).
 Learning polynomials with queries: The highly noisy case.
Proceedings 36th IEEE Conference on Foundations of Computer Science.
October 1995, 294303 (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, 332341 (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. 427436
(with D. Ron).
 On learning boundedwidth branching programs. Proceedings 8th Annual
ACM Workshop on Computational Learning Theory, 1995, 361368 (with
F. Ergun and S. Ravikumar).
Return to:

19951996 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).