Online Papers:

  • Rubinfeld, R., "Sublinear time algorithms".
  • Raskhodnikova, S., Ron, D., Rubinfeld, R., Smith, A., Sublinear Algorithms for Approximating String Compressibility Proceedings of RANDOM-APPROX 2007.
  • Rubinfeld, R., Servedio, R. Testing monotone high-dimensional distributions, Proceedings of STOC 2005, pp. 147-156.
  • Ben Or, M., Coppersmith, D., Luby, M., Rubinfeld, R., ``Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions'', Abstract to appear in Proceedings of RANDOM 2004.
  • Batu, T., Kumar, R., Rubinfeld, R., ``Sublinear algorithms for testing monotone and unimodal distributions'', Proceedings of STOC 2004.
  • Chazelle, B., Kilian, J., Rubinfeld, R., Tal, A., ``The Bloomier filter: an efficient data structure for static support lookup tables'', Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04). pp. 30-39.
  • Batu, T., Ergun, F., Kilian, J., Magen, A., Raskhodnikova, S., Rubinfeld, R., Sami, R., ``A sublinear algorithm for weakly approximating edit distance'', STOC 2003, pp. 316-324.
  • Kumar, R., Rubinfeld, R., ``Sublinear time algorithms'', Samir Khuller's Algorithms column in SIGACT News 2003.
  • A. Czumaj, F. Ergun, L. Fortnow, A. Magen, I. Newman, R. Rubinfeld, and C. Sohler, ``Sublinear-time Approximation of Euclidean Minimum Spanning Tree'', Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03), pp. 813-822.
  • Parnas, M., Ron, D., Rubinfeld, R., `` On Testing Convexity and Submodularity''. SIAM J. Comput. 32(5). pp. 1158-1184, 2003. Preliminary abstract in Proceedings of the Sixth International Workshop on Randomization and Approximation Techniques in Computer Science - APPROX-RANDOM'02.
  • Batu, T., Dasgupta, S., Kumar, R., Rubinfeld, R., ``The complexity of approximating the entropy'', in proceedings of STOC 2002. pp. 678-687. Abstract in proceedings of Computational Complexity 2002, p.17.
  • Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A., ``Monotonicity testing over general poset domains'', in proceedings of STOC 2002, pp. 474-483.
  • Batu, T., Fischer, E., Fortnow, L., Kumar, R., Rubinfeld, R., White, P., ``Testing random variables for independence and identity'', Proc. 42nd IEEE Conference on Foundations of Computer Science, 2001.
  • Canetti, R., Ishai, Y., Kumar, R., Reiter, M, Rubinfeld, R., Wright, R., ``Selective private function evaluation with applications to private statistics'', Proc. Principles of Distributed Computing (PODC), 2001.
  • Chazelle, B., Rubinfeld, R., Trevisan, L., ``Approximating the minimum spanning tree weight in sublinear time'', Proceedings of ICALP, 2001.
  • Parnas, M., Ron, D., Rubinfeld, R., ``Testing membership in parenthesis languages''. Random Struct. Algorithms 22(1), pp. 98-138 (2003). Preliminary abstract in Proceedings of the Fifth International Workshop on Randomization and Approximation Techniques in Computer Science - APPROX-RANDOM'01.
  • Batu, T., Fortnow, L., Rubinfeld, R., Smith, W.D., White, P., ``Testing the closeness of distributions'', Proc. 41st IEEE Conference on Foundations of Computer Science}, 2000.
  • Fagin, R., Karlin, A., Kleinberg, J., Raghavan, P., Rajagopalan, S., Rubinfeld, R., Sudan, M., Tomkins, A., ``Random Walks with `Back Buttons' '', {\em Annals of Applied Probability} 2001, Vol. 11, No. 3. pp. 810-862. Preliminary abstract in {\em Proc. 32nd ACM Symposium on Theory of Computing}, 2000.
  • Batu, T., Rubinfeld, R., White, P., ``Fast Approximate PCPs for Multidimensional Bin-packing Problems.'' Proceedings of the Third International Workshop on Randomization and Approximation Techniques in Computer Science - APPROX-RANDOM'99 (D. Hochbaum, K. Jansen, J.P.D. Rolim, and A. Sinclair editors), pp. 245-256, Springer-Verlag LNCS 1671, Berkeley, CA, August 1999.
  • Batu, T., Rubinfeld, R., White, P., "Runtime Verification of Remotely Executed Code using Probabilistically Checkable Proof Systems", in the Proceedings of the Workshop on Run-Time Result Verification - RTRV'99, Trento, Italy, July 1999.
  • Ergun, F., Kumar, S. Ravi, Rubinfeld, R., ``Fast PCPs for optimization problems'', To appear in Information and Computation. Preliminary version in Proc. 31st ACM Symposium on Theory of Computing, 1999.
  • Funda Ergun, Sampath Kannan, S. Ravi Kumar, Ronitt Rubinfeld, Mahesh Vishwanthan, ``Spot-checkers'', JCSS 60, 717-751 (2000). Preliminary abstract appears in in Proc. 30th ACM Symposium on Theory of Computing, 1998.
  • 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.
  • Funda Ergun, S. Ravi Kumar, Ronitt Rubinfeld, ``Approximate Checking of Polynomials and Functional Equations'', SIAM J. of Computing, 31 (2): 550--576. Preliminary abstract in Proc. 37th IEEE Conference on Foundations of Computer Science, 1996.
  • Kleinberg, J., Rubinfeld, R., ``Short Paths in Expander Graphs'', In Proc. 37th IEEE Conference on Foundations of Computer Science, 1996.
  • Ronitt Rubinfeld, Madhu Sudan, ``Robust Characterizations of Polynomials and their Applications to Program Testing.'' In SIAM J. of Computing, April 1996.
  • Ronitt Rubinfeld. ``Designing Checkers for Programs that Run in Parallel.'' In Algorithmica, April 1996.
  • 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.
  • Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan, ``Learning polynomials with queries: the highly noisy case.'' SIAM J. of Discrete Mathematics, 13(4):535--570, November 2000. Preliminary version in Proc. 36th IEEE Conference on Foundations of Computer Science, 1995.
  • 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.
  • 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.
  • Ronitt Rubinfeld, ``Robust Functional Equations and their Applications to Program Testing.'' SIAM J. of Computing, Vol. 28, No. 6, pp. 1972-1997. Preliminary version in Proc. 35th IEEE Conference on Foundations of Computer Science, 1994.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.