List of Papers

  • Approximating and Testingk-Histogram Distributions in Sub-linear time, by Indyk, P., Levi, R., and Rubinfeld, R. To appear in Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2012), Scottsdale, Arizona, May 2012. Also, Electronic Colloquium on Computational Complexity (ECCC), volume 18, TR11-171, December, 2011.
  • Sublinear Time Algorithms, by Rubinfeld, R. and Shapira, A. SIAM Journal of Discrete Mathematics, 25(4):1562-1588, 2012. Also, Electronic Colloquium on Computational Complexity (ECCC) volume 18, TR11-013, February 2011.
  • A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size, by Onak, K., Ron, D., Rosen, M., and Rubinfeld, R. Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), San Francisco, CA, pages 1123-1131, January 2012. Also, CoRR abs/1110.1079v1, October 2011.
  • Space-efficient Local Computation Algorithms, by Alon, N., Rubinfeld, R., Vardi, S., and Xie, N. Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), San Francisco, CA, pages 1132-1139, January 2012. Also, CoRR abs/1109.6178v2, September 2011.
  • Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity, by Ron, D., Rubinfeld, R., Safra, M., and Weinstein, O. In L.A. Goldberg, K. Jansen, R. Ravi, J. D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011, volume 6845 of Lecture Notes in Computer Science, pages 664-675, 2011. Springer. Also, CoRR abs/1101.5345v1, January 2011.
  • Testing Properties of Collections of Distributions, by Levi, R., Ron, D., and Rubinfeld, R. Innovations in Computer Science (ICS 2011), Beijing, China, pages 179-194, January 2011. Also, Electronic Colloquium on Computational Complexity (ECCC), volume 17, Revision of TR10-157, April 2011.
  • Fast Local Computation Algorithms, by Rubinfeld, R, Tamir, G., Vardi, S., and Xie, N. Innovations in Computer Science (ICS 2011), Beijing, China, pages 223-238, January 2011. Also, CoRR abs/1104.1377v1, April 2011.
  • Testing monotonicity of distributions over general partial orders, by Bhattacharyya, A., Fischer, E., Rubinfeld, R., and Valiant, P. Innovations in Computer Science (ICS 2011), Beijing, China, pages 239-252, January 2011. Also, Electronic Colloquium on Computational Complexity (ECCC) volume 17, TR10-027, February 2010.
  • Sublinear Time Algorithms for Earth Mover's Distance, Do Ba, K., Nguyen, H.L., Nguyen, H.N.,and Rubinfeld, R. Theory of Computing Systems, 48(2): 428-442, 2011. Also, CoRR abs/0904.0292v1, April 2009.
  • Testing Non-uniform k-Wise Independent Distributions over Product Spaces, by Rubinfeld, R., and Xie, N. In S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, P. G. Spirakis, editors, Automata, Lanuages, and Programming: 37th International Colloquium (ICALP 2010 Part I), volume 6198 of Lecture Notes in Computer Science, pages 565-581, 2010.
  • Sublinear Algorithms in the External Memory Model, by Andoni, A., Indyk, P., Onak, K., and Rubinfeld, R. In O. Goldreich, editor, Property Testing - Current Research and Surveys, volume 6390 of Lecture Notes in Computer Science, pages 240-243, January 2010.
  • Testing (Subclasses of) Halfspaces, by Matulef, K., O'Donnell, R., Rubinfeld, R., and Servedio, R. In O. Goldreich, editor, Property Testing - Current Research and Surveys, volume 6390 of Lecture Notes in Computer Science, pages 334-340, January 2010.
  • Dynamic Approximate Vertex Cover and Maximum Matching, Onak, K. and Rubinfeld, R. In O. Goldreich, editor, Property Testing - Current Research and Surveys, volume 6390 of Lecture Notes in Computer Science, pages 341-345, January 2010.
  • Maintaining a large matching and a small vertex cover, by Onak, K. and Rubinfeld, R. Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), Cambridge, MA, pages 457-464, June 2010.
  • A local decision test for sparse polynomials, by Grigorescu, E., Jung, K., and Rubinfeld, R. Information Processing Letters, 110(20):898-901, 2010.
  • Testing halfspaces, by Matulef, K., O'Donnell, R., Rubinfeld, R., and Servedio, R. SIAM Journal on Computing, 39(5): 2004-2047, 2010. Also, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pages 256-264, New York, NY, January 4-6, 2009. And, Electronic Colloquium on Computational Complexity (ECCC), volume 14, TR07-128, December 2007.
  • Improved Recommendations via (More) Collaboration, by Boim, R., Kaplan, H., Milo, T., and Rubinfeld, R. Proceedings of the 13th International Workshop on the Web and Databases (WebDB 2010), Indianapolis, Indiana, June, 2010.
  • Testing Closeness of Discrete Distributions, by Batu, T., Fortnow, L., Rubinfeld, R., Smith, W. D., and White, P. CoRR abs/1009.5397v2, September 2010.
  • Testing -1,1-Weight Halfspace, by Matulef, K., O'Donnell, R., Rubinfeld, R., and Servedio, R. In I. Dinur, K. Jansen, J. Naor, J. D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009, volume 5687 of Lecture Notes in Computer Science, pages 646-657, 2009. Springer.
  • External Sampling, by Andoni, A., Indyk, P., Onak, K, and Rubinfeld, R. In S. Alberts, A. Marchetti-Spaccamela, Y. Matias, S. E. Nikoletseas, W. Thomas, editors, Automata, Languages, and Programming: 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Rhodes, Greece, July 2009, volume 5555 of Lecture Notes in Computer Science, pages 83-94, 2009. Springer.
  • Linearity Testing/Testing Hadamard Codes, by Ronitt Rubinfeld. Encyclopedia of Algorithms, Springer, 2008.
  • Testing k-wise and almost k-wise independence, by Alon, N., Andoni, A., Kaufman, T., Matulef, K., Rubinfeld, R., and Xie, N. Proceedings of the 39th ACM Symposium on Theory of Computing (STOC 2007), pages 496-505, San Diego, CA, June 2007.
  • Testing for concise representations, by Diakonikolas, I., Lee, H., Matulef, K., Onak, K., Rubinfeld, R., Servedio, R., and Wan, A. Proceedings of the 48th Annual Symposium on Foundations of Computer Science (FOCS 2007), pages 549-558, Providence, RI, October 2007. Also, Electronic Colloquium on Computational Complexity (ECCC), volume 14, TR07-077, August 2007.
  • Sublinear Algorithms for Approximating String Compressibility, by Raskhodnikova, S., Ron, D., Rubinfeld, R., and Smith, A. In M. Charikar, K. Jansen, O. Reingold, and J. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop (APPROX 2007) and 11th International Workshop (RANDOM 2007), Princeton, NJ, August 20-22, 2007, volume 4627 of Lecture Notes in Computer Science, pages 609-623, 2007. Springer. Also, CoRR, Abs/0706.1084, June 2007, and Algorithmica, Online First, February 2012.
  • Tolerant property testing and distance approximation., by Parnas, M., Ron, D., and Rubinfeld, R. Journal of Computer and System Sciences, 72(6):1012-1042, 2006. Also, Electronic Colloquium on Computational Complexity (ECCC), volume 11, TR04-010, February 2004.
  • Sublinear Time Algorithms, by Rubinfeld, R. In M. Sanz-Sole, J. Soria, J. L. Varona, and J. Verdera, editors, Proceedings of the International Congress of Mathematicians, Madrid, Spain, August 22-30, 2006, volume III, pages 1095-1110, European Mathematical Soceity, Zurich, Switzerland, 2006.
  • Testing monotone high-dimensional distributions, by Rubinfeld, R. and Servedio, R. Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005), pages 147-156, Baltimore, MD, May 2005. Random Structures and Algorithms, 34(1):24-44, 2009.
  • Fast Approximate PCPs for Multidimensional Bin-packing Problems, by Batu, T., Rubinfeld, R., and White, P. Information and Computation, 196(1):42-56, 2005. Preliminary version in D. Hochbaum, K. Jansen, J. Rolim, and A. Sinclair, editors, Randomization, Approximation, and Combinatorial Algorithms and Techniques, Third International Workshop on Randomization and Approximation Techniques in Computer Science and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (RANDOM-APPROX'99), Berkeley, CA, USA, August 8-11, 1999, volume 1671 of Lecture Notes in Computer Science, pages 245-256, 1999. Springer.
  • The complexity of approximating the entropy, by Batu, T., Dasgupta, S., Kumar, R., and Rubinfeld, R. SIAM Journal on Computing, 35(1):132-150, 2005. Preliminary version in Proceedings of the 34th ACM Symposium on Theory of Computing (STOC 2002), pages 678-687, Montreal, Canada, May 2002.
  • Approximating the minimum spanning tree weight in sublinear time, by Chazelle, B., Rubinfeld, R., and Trevisan, L. SIAM Journal on Computing, 34(6):1370-1379, 2005. Preliminary version in F. Orejas, P. Spirakis, and J. van Leeuwen, editors, Automata, Languages, and Programming: 28th International Colloquium (ICALP 2001), Crete Greece, July 8-12, 2001, volume 2076 of Lecture Notes in Computer Science, pages 190-200, 2001. Springer.
  • Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time, by Czumaj, A., Ergun, F., Fortnow, L., Magen, A., Newman, I., Rubinfeld, R., and Sohler, C. SIAM Journal on Computing, 35(1):91-109, 2005. Preliminary version in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pages 813-822, Baltimore, MD, January 2003. (Title: Sublinear-time approximation of Euclidean minimum spanning tree.)
  • Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size, by Raskhodnikova, S., Ron, D., Shpilka, A., and Smith, A. Electronic Colloquium on Computational Complexity (ECCC), volume 12, TR05-125, November 2005.
  • Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions, by Ben-Or, M., Coppersmith, D., Luby, M., and Rubinfeld, R. In K. Jansen, S. Khanna, J. Rolim, and D. Ron, editors, Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2004) and 8th International Workshop on Randomization and Computation (RANDOM 2004), Cambridge, MA, August 22-24, 2004, volume 3122 of Lecture Notes in Computer Science, pages 273-285, 2004. Springer. Also, Electronic Colloquium on Computational Complexity (ECCC), volume 11, TR04-052, June 2004. And Random Structures and Algorithms, 32(1):49-70, 2008.
  • Sublinear algorithms for testing monotone and unimodal distributions, by Batu, T., Kumar, R., and Rubinfeld, R. Procedings of the 36th ACM Symposium on Theory of Computing (STOC 2004), pages 381-390, Chicago, IL, June 2004.
  • The Bloomier filter: an efficient data structure for static support lookup tables, by Chazelle, B., Kilian, J., Rubinfeld, R., Tal, A. Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pages 30-39, New Orleans, LA, January 2004.
  • Fast Approximate Probabilistically Checkable Proofs, by Ergun, F., Kumar, S. Ravi, and Rubinfeld, R. Information and Computation, 189(2):135-159, 2004. Preliminary abstract in Proceedings of the 31st ACM Symposium on Theory of Computing (STOC 1999), pages 41-50, Atlanta, GA, May 1999.
  • A sublinear algorithm for weakly approximating edit distance, by Batu, T., Ergun, F., Kilian, J., Magen, A., Raskhodnikova, S., Rubinfeld, R., and Sami, R. Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003), pages 316-324, San Diego, CA, June 2003.
  • Sublinear time algorithms, by Kumar, R. and Rubinfeld, R., Samir Khuller's SIGACT News column, 2003.
  • Testing Membership in Parenthesis Languages, by Parnas, M., Ron, D., and Rubinfeld, R. Random Structures and Algorithms, 22(1):98-138, 2003. Preliminary abstract in M. Goemans, K. Jansen, J. Rolim, and L. Trevisan, editors, Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2001) and 5th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 2001), Berkeley, CA, USA, August 18-20, 2001, volume 2129 of Lecture Notes in Computer Science, pages 261-272, 2001. Springer.
  • On Testing Convexity and Submodularity, by Parnas, M., Ron, D., and Rubinfeld, R. SIAM Journal on Computing, 32(5):1158-1184, 2003. Prelminary version in J. Rolim and S. Vadhan, editors, Randomization and Approximation Techniques, 6th International Workshop, (RANDOM 2002), Cambridge, MA, September 13-15, 2002, volume 2483 of Lecture Notes in Computer Science, pages 11-25, 2002. Springer.
  • Monotonicity testing over general poset domains, by Fischer, E., Lehman, E., Newman, I., and Raskhodnikova, S. Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002), pages 474-483, Montreal, Canada, May 2002.
  • Testing random variables for independence and identity, by Batu, T., Fischer, E., Fortnow, L., Kumar, R., Rubinfeld, R., and White, P. Proceedings of the 42nd IEEE Conference on Foundations of Computer Science (FOCS 2001), pages 442-451, Las Vegas, NV, October 2001.
  • Selective private function evaluation with applications to private statistics, by Canetti, R., Ishai, Y., Kumar, R., Reiter, M, Rubinfeld, R., and Wright, R. Proceedings of the 20th ACM Symposium on Principles of Distributed Computing (PODC 2001), pages 293-304, Newport, RI, August 2001.
  • Checking Approximate Computations of Polynomials and Functional Equations, by Ergun, F., Kumar, S. Ravi, and Rubinfeld, R. SIAM Journal on Computing, 31(2):550-576, 2001. Proceedings of the 37th IEEE Conference on Foundations of Computer Science (FOCS 1996), pages 592-601, Burlington, Vermont, October 1996.
  • Random Walks with `Back Buttons, by Fagin, R., Karlin, A., Kleinber, J., Raghavan, P., Rajagopalan, S., Rubinfeld, R., Sudan, M., and Tomkins, A. Annals of Applied Probability, 11(3):810-862, 2001. Preliminary abstract in Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC 2000), pages 315-324, Portland, OR, May 2000.
  • Testing that Distributions are Close, by Batu, T., Fortnow, L., Rubinfeld, R., Smith, W.D., and White, P. Proceedings of the 41st IEEE Conference on Foundations of Computer Science (FOCS 2000), pages 259-269, Redondo Beach, CA, November 2000.
  • Spot Checkers, by Ergun, F., Kannan, S., Kumar, R., Rubinfeld, R., and Vishwanathan, M. Journal of Computer and System Sciences, 60(3):717-751, June, 2000.Special issue on STOC 1998. Preliminary abstract in Proceedings of the 30th ACM Symposium on Theory of Computing (STOC 1998), pages 259-268, Dallas, TX, May 1998.
  • Learning polynomials with queries: the highly noisy case, by Goldreich, O., Rubinfeld, R., and Sudan, M. SIAM Journal on Discrete Mathematics, 13(4):535--570, November, 2000. Also, Electronic Colloquium on Computational Complexity (ECCC), volume 5, TR98-060, October 1998 and Preliminary abstract in Proceedings of the 36th IEEE Conference on Foundations of Computer Science (FOCS 1995), pages 294-303, Milwaukee, WI, October 1995.
  • Runtime Verification of Remotely Executed Code using Probabilistically Checkable Proof Systems, by Batu, T., Rubinfeld, R., and White, P. Workshop on Run-Time Result Verification - FLoC'99, Trento, Italy, July 1999.
  • On the Robustness of Functional Equations, by Rubinfeld, R. SIAM Journal on Computing, 28(6):1972-1997, 1999. Preliminary abstract in Proceedings of the 35th IEEE Conference on Foundations of Computer Science (FOCS 1994), pages 288-299, Santa Fe, New Mexico, November 1994.
  • Reconstructing Algebraic Functions from Mixed Data, by Ar, S., Lipton, R., Rubinfeld, R., and Sudan, M. SIAM Journal on Computing, 28(2):487-510, 1998. Preliminary abstract appears in Proceedings of the 33rd IEEE Conference on Foundations of Computer Science (FOCS 1992), pages 503-512, Pittsburgh, PA, October 1992.
  • Learning distributions from random walks, by Ergun, F., Kumar, S. Ravi, and Rubinfeld, R. Proceedings of the 10th Annual ACM Workshop on Computational Learning Theory (COLT 1997), pages 243-249, Nashville, TN, July 1997.
  • Efficient Learning of Typical Finite Automata from Random Walks, by Freund, Y., Kearns, M., Ron, D., Rubinfeld, R., Schapire, R., and Sellie, L. Information and Computation, 138(1):23-48, 1997. Also, Proceedings of the 25th ACM Symposium on Theory of Computing (STOC 1993), pages 315-324, San Diego, CA, May 1993. Preliminary Abstract.
  • Exactly Learning Automata with Small Cover Time, by Ron, D. and Rubinfeld, R. Machine Learning,27(1):69-96, April 1997. Special issue on COLT 1995. Also, Preliminary abstract in Proceedings of the 8th Annual ACM Workshop on Computational Learning Theory (COLT), pages 427-436, Santa Cruz, CA, 1995.
  • Short Paths in Expander Graphs, by Kleinberg, J., and Rubinfeld, R. Proceedings of the 37th IEEE Conference on Foundations of Computer Science (FOCS 1996), pages 86-95, Burlington, Vermont, October 1996.
  • Designing Checkers for Programs that Run in Parallel, by Rubinfeld, R. Algorithmica, 15(4):287-301, April 1996.
  • Robust Characterizations of Polynomials with Applications to Program Testing, by Rubinfeld, R., and Sudan, M. SIAM Journal on Computing, 25(2):252-271, April, 1996.
  • On Learning Bounded-Width Branching Programs, by Ergun, F., Kumar, S. Ravi, and Rubinfeld, R. Proceedings of the 8th Annual ACM Workshop on Computational Learning Theory (COLT 1995), Santa Cruz, CA, pages 361-368, 1995.
  • Efficient algorithms for learning to play repeated games against computationally bounded adversaries, by Freund, Y., Kearns, M., Mansour, Y., Ron, D., Rubinfeld, R., and Schapire, R. Proceedings of the 36th IEEE Conference on Foundations of Computer Science (FOCS 1995), pages 332-341, Milwaukee, WI, October 1995.
  • Learning Fallible Deterministic Finite Automata, by Ron, D., and Rubinfeld, R. Machine Learning, 18(2-3):149-185, 1995. (Special issue of COLT 1993). Also, Proceedings of the 6th Annual ACM Workshop on Computational Learning Theory (COLT 1993), pages 218-227, Santa Cruz, CA, July 1993.
  • On the Learnability of Discrete Distributions, by Kearns, M., Mansour, Y., Ron, D., Rubinfeld, R., Schapire, R., and Sellie, L. Proceedings of the 26th ACM Symposium on Theory of Computing (STOC 1994), pages 273-282, Montreal, Canada, May 1994.
  • A New Modular Interpolation Algorithm for Factoring Multivariate Polynomials, by Rubinfeld, R., and Zippel, R. L. Adleman and M-D. Huang, editors, Algorithmic Number Theory, First International Symposium, ANTS-1, Ithaca, NY, May 1994, volume 877 of Lecture Notes in Computer Science, pages 93-107, Springer, 1994. Also, Cornell CS Tech. Report 93--1326, January 1993.
  • Self-Testing/Correcting with Applications to Numerical Problems, by Blum, M., Luby, M., and Rubinfeld, R. Journal of Computer and System Sciences, 47(3):549-595, December 1993. (Special issue of STOC 1990). Proceedings of the 22nd ACM Symposium on Theory of Computing (STOC 1990), pages 73--83, Baltimore, MD, May 1990. Prelminary Abstract.
  • On the Time and Space Complexity of Computation Using Write-Once Memory, Or Is Pen Really Much Worse Than Pencil? by Irani, S., Naor, M., and Rubinfeld, R. Mathematical Systems Theory, 25(2):141-159, 1992. Technical Report CSD-88-434, University of California-Berkeley, June 1988.
  • Interactive Proofs with Space Bounded Provers, by Kilian, J., and Rubinfeld, R. In J. Feigenbaum, editor, Advances in Cryptology - CRYPTO 1991, 11th Annual International Cryptology Conference, Santa Barbara, CA, August 11-15, 1991, volume 576 of Lecture Notes in Computer Science, pages 225-231, 1992. Springer.
  • Self-Testing Polynomial Functions Efficiently and Over Rational Domains, by Rubinfeld, R., and Sudan, M. Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1992), pages 23-32, Orlando, FL, January 1992.
  • Batch Checking with Applications to Linear Functions, by Rubinfeld, R. Information Processing Letters, 42(2):77-80, May, 1992.
  • Program Result Checking Against Adaptive Programs and in Cryptographic Settings, by Blum, M., Luby, M., and Rubinfeld, R. Distributed Computing and Cryptography, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 2, 1991.
  • Self-Testing/Correcting for Polynomials and Approximate Functions, by Gemmell, P., Lipton, R., Rubinfeld, R., Sudan, M., and Wigderson, A. Proceedings of the 23rd ACM Symposium on Theory of Computing (STOC 1991), pages 32-42, New Orleans, LA, May 1991.
  • A Competitive 2-Server Algorithm, by Irani, S., and Rubinfeld, R.,
  • Information Processing Letters, 39(2):85-91, July, 1991.
  • The Cover Time of a Regular Expander is $O(n \log n)$, by Rubinfeld, R. Information Processing Letters,35(1):49-51, June 1990.
  • A Mathematical Theory of Self-Checking, Self-Testing and Self-Correcting Programs, by Rubinfeld, R. PhD Thesis, U.C. Berkeley, August 1990. ICSI Technical Report No. TR-90-054.
  • Reversing Trains: A Turn of the Century Sorting Problem, by Amato, N., Blum, M., Irani, S., and Rubinfeld, R. Journal of Algorithms, 10(3):413-428, September, 1989.
  • Automatic Evaluation of Two-Fingered Grips, by Barber, J., Volz, R., Desai, R., Rubinfeld, R., Schipper, B., and Wolter, J. IEEE Journal of Robotics and Automation, RA-3(4):356-361, August, 1987.