Some recent papers:

Checking

  1. Funda Ergun, Sampath Kannan, S. Ravi Kumar, Ronitt Rubinfeld, Mahesh Vishwanthan, ``Spot-checkers'', Preliminary abstract appears in in Proc. 30th ACM Symposium on Theory of Computing, 1998.
  2. S. Ravi Kumar, Ronitt Rubinfeld, ``Property Testing of Abelian Group Operations''
  3. Funda Ergun, S. Ravi Kumar, Ronitt Rubinfeld, ``Approximate Checking of Polynomials and Functional Equations'', In Proc. 37th IEEE Conference on Foundations of Computer Science, 1996.
  4. Ronitt Rubinfeld, ``Robust Functional Equations and their Applications to Program Testing.'' Preliminary version in Proc. 35th IEEE Conference on Foundations of Computer Science, 1994.
  5. Ronitt Rubinfeld, Madhu Sudan, ``Robust Characterizations of Polynomials and their Applications to Program Testing.'' In SIAM J. of Computing, April 1996.
  6. Ronitt Rubinfeld. ``Designing Checkers for Programs that Run in Parallel.'' In Algorithmica, April 1996.
  7. Blum, M., Luby, M., Rubinfeld, R., ``Self-Testing/Correcting with Applications to Numerical Problems,'' In J. Comp. Sys. Sci. Vol. 47, No. 3, December 1993 (special issue on STOC 1990). Preliminary abstract appears in Proc. 22th ACM Symposium on Theory of Computing, 1990.
  8. Rubinfeld, R., ``A Mathematical Theory of Self-Checking, Self-Testing and Self-Correcting Programs'' , PhD Thesis, U.C. Berkeley, August 1990. ICSI Technical Report No. TR-90-054.

Learning Theory

  1. Freund, Y., Kearns, M., Ron, D., Rubinfeld, R., Schapire, R., Sellie, L., ``Efficient Learning of Typical Finite Automata from Random Walks'', To appear in Information and Computation. Preliminary abstract appears in in Proc. 25rd ACM Symposium on Theory of Computing, 1993, pp. 315-324.
  2. Kearns, M., Mansour, Y., Ron, D., Rubinfeld, R., Schapire, R., Sellie, L., ``On the Learnability of Discrete Distributions'', in Proc. 26th ACM Symposium on Theory of Computing, pp. 273-282, 1994.
  3. Yoav Freund, Michael Kearns, Yishai Mansour, Dana Ron, Ronitt Rubinfeld. ``Efficient algorithms for learning to play repeated games against computationally bounded adversaries.'' In Proc. 36th IEEE Conference on Foundations of Computer Science, 1995.
  4. Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan, ``Learning polynomials with queries: the highly noisy case.'' In Proc. 36th IEEE Conference on Foundations of Computer Science, 1995.
  5. Ron, D., Rubinfeld, R., ``Exactly Learning Automata with Small Cover Time'', Machine Learning 27, 69-96 (1997) (special issue on COLT '95). Preliminary abstract in Proc. of the 8th Annual ACM Workshop on Computational Learning Theory, 1995.
  6. Ron, D., Rubinfeld, R., ``Learning Fallible Finite State Automata'', Machine Learning, 18, pp. 149-185 (1995) (special issue on COLT '93). Preliminary abstract in Proc. of the 6th Annual ACM Workshop on Computational Learning Theory, 1993.
  7. Ar, S., Lipton, R., Rubinfeld, R., Sudan, M., ``Reconstructing Algebraic Functions from Mixed Data'', Preliminary version appears in Proc. 33rd IEEE Conference on Foundations of Computer Science, pp.503-512, 1992. To appear in SIAM J. of Computing.
  8. Funda Ergun, S. Ravi Kumar, Ronitt Rubinfeld, ``On Learning Bounded-Width Branching Programs'', Proc. of the 8th Annual ACM Workshop on Computational Learning Theory, pp.361-368, 1995.
  9. Funda Ergun, S. Ravi Kumar, Ronitt Rubinfeld, ``Learning distributions from random walks'', Proc. of the 10th Annual ACM Workshop on Computational Learning Theory, pp.361-368, 1997.

Other papers:

  1. Kleinberg, J., Rubinfeld, R., ``Short Paths in Expander Graphs'', In Proc. 37th IEEE Conference on Foundations of Computer Science, 1996.
  2. Ronitt Rubinfeld, R. Zippel, ``A New Modular Interpolation Algorithm for Factoring Multivariate Polynomials.'' In proceedings of Algorithmic Number Theory Symposium, May 1994. Also available as Cornell CS Tech. Report 93--1326, January 1993.

Some slides of talks:

    Using properties to test functions
    Implementations of Result Checkers