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.