# Ronitt Rubinfeld: Papers - Bibliographic Information

**2015**

**Brief Announcement: Local Computation Algorithms for Graphs of Non-Constant Degrees**, by Levi, R., Rubinfeld, R., and Yodpinyanee, A. *Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015*, pages 59-61, Portland, Oregon, June 2015. Also, CoRR abs/1502.04022, 2015.

**Rapid Sampling for Visualizations with Ordering Guarantees,** by Kim, A., Blais, E., Parameswaran, A. G., Indyk, P., Madden, S., and Rubinfeld, R. *Proceedings of the VLDB Endowment: 41st International Conference on Very Large Data Bases, Kohala Coast, Hawaii, August 31-September 4, 2015,* 8(5):521-532, 2015. Also, CoRR abs/1412.3040, 2014.

**A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness**, by Devadas, S. and Rubinfeld, R., *Theory of Computing Systems,* published online June 2015. Also, CoRR abs/1412.5484, 2014.

**Constructing Near Spanning Trees with Few Local Inspections,** by Levi, R., Moshkovitz, G., Ron, D., Rubinfeld, R., and Shapira, A. Electronic Colloquium on Computational Complexity (ECCC) TR15-019, February 2015. Also, CoRR abs/1502.00413, 2015.

Sampling Correctors, by Canonne, C. L., Gouleakis, T., and Rubinfeld, R. To appear in *7th Annual Innovations in Theoretical Computer Science (ITCS),* Cambridge, MA, January 2016. Also, CoRR abs/1504.06544, 2015.

**Testing Shape Restrictions of Discrete Distributions,** by Canonne, C. L., Diakonikolas, I., Gouleakis, T., and Rubinfeld, R. CoRR abs/1507.03558, 2015.

**2014**

**A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness**, by Devadas, S. and Rubinfeld, R., CoRR abs/1412.5484, 2014.

**Testing Similar Means,** by Levi, R., Ron, D., and Rubinfeld, R. *SIAM Journal on Discrete Mathematics,* 28(4):1699-1724, 2014. Earlier versions in Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, Roger Wattenhofer, editors, *Automata, Languages, and Programming - 39th International Colloquium (ICALP 2012), Warwick, UK, July 9-13, 2012, Part I,* volume 7391 of *Lecture Notes in Computer Science*, pages 629-640, Springer, 2012. Also, Electronic Colloquium on Computational Complexity (ECCC) TR12-055, May 2012.

**Local Algorithms for Sparse Spanning Graphs**, by Levi, R., Ron, D., and Rubinfeld, R. *Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014*, Barcelona, Spain, September 4-6, 2014, pages 826-842, September 2014. Also, CoRR abs/1402.3609, 2014.

**Testing Probability Distributions Underlying Aggregated Data,** by Canonne, C. L., Rubinfeld, R. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias, editors, *Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I*, volume 8572 of *Lecture Notes in Computer Science*, pages 283-295, 2014. Springer. Also, Electronic Colloquium on Computational Complexity (ECCC) TR14-021, February 2014 and CoRR abs/1402.3835, 2014.

**Rapid Sampling for Visualizations with Ordering Guarantees,** by Kim, A., Blais, E., Parameswaran, A. G., Indyk, P., Madden, S., and Rubinfeld, R. CoRR abs/1412.3040, 2014.

**2013**

**Local Reconstructors and Tolerant Testers for Connectivity and Diameter,** by Campagna, A., Guo, A., and Rubinfeld, R. In Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jensen, and Jose D. Rolim, editors, *Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013,* volume 8096 of *Lecture Notes in Computer Science,* pages 411-424, 2013. Springer. Also, CoRR abs/1208.2956, 2012.

**A Simple Online Competitive Adaptation of Lempel-Ziv Compression with Efficient Random Access Support,** by Dutta, A., Levi, R., Ron, D., and Rubinfeld, R. *Proceedings of the 2013 Data Compression Conference (DCC 2013)*, Snowbird, UT, March 2013. Also, CoRR abs/1301.2495, 2013.

**Robust Characterizations of k-wise Independence over Product Spaces and Related Testing Results,** by Rubinfeld, R. and Xie, N. *Random Structures and Algorithms*, 43(3):265-312, 2013. Published online in May 2012.

**Testing Closeness of Discrete Distributions,** by Batu, T., Fortnow, L., Rubinfeld, R., Smith, W. D., and White, P. *Journal of the ACM,* 60(1):4, 2013. Also,
CoRR abs/1009.5397v2, September 2010.

**Sublinear Algorithms for Approximating String Compressibility,** by Raskhodnikova, S., Ron, D., Rubinfeld, R., and Smith, A. *Algorithmica,* 65(3):685-709, 2013. Earlier version 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.

**Testing Properties of Collections of Distributions,** by Levi, R., Ron, D., and Rubinfeld, R. *Theory of Computing,* 9:295-347,2013. Earlier version in *Innovations in Computer Science (ICS 2011)*, Beijing, China, pages 179-194, January 2011. Also, Electronic Colloquium on Computational Complexity (ECCC) TR10-157 (Revision), April 2011.

**2012**

**Taming Big Probability Distributions, ** by Rubinfeld, R. *ACM Crossroads*, 19(1):24-28,2012.

**Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity**, by Ron, D., Rubinfeld, R., Safra, M., Samorodnitsky, A., and Weinstein, O. *ACM Transactions on Computation Theory,* 4(4):11, 2012. Earlier version 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 Similar Means,** by Levi, R., Rubinfeld, R., and Ron, D. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, Roger Wattenhofer, editors, *Automata, Languages, and Programming - 39th International Colloquium (ICALP 2012), Warwick, UK, July 9-13, 2012, Part I,* volume 7391 of *Lecture Notes in Computer Science*, pages 629-640, Springer, 2012. Also, Electronic Colloquium on Computational Complexity (ECCC) TR12-055, May 2012.

**Approximating and Testing ***k-*Histogram Distributions in Sub-linear time, by Indyk, P., Levi, R., and Rubinfeld, R.
*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) TR11-171, December, 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.

**Local reconstructors and tolerant testers for connectivity and diameter,** by Campagna, A., Guo, A., and Rubinfeld, R. CoRR abs/1208.2956, August 2012.

**2011**

**Sublinear Time Algorithms, ** by Rubinfeld, R. and Shapira, A.
*SIAM Journal of Discrete Mathematics*, 25(4):1562-1588, 2011.
Also, Electronic Colloquium on Computational Complexity (ECCC) TR11-013, February 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) TR10-157 (Revision), 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) 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.

**Approximating and Testing ***k-*Histogram Distributions in Sub-linear time, by Indyk, P., Levi, R., and Rubinfeld, R.
Electronic Colloquium on Computational Complexity (ECCC) TR11-171, December, 2011.

**A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size,** by Onak, K., Ron, D., Rosen, M., and Rubinfeld, R., CoRR abs/1110.1079v1, October 2011.

**Space-efficient Local Computation Algorithms,** by Alon, N., Rubinfeld, R., Vardi, S., and Xie, N. CoRR abs/1109.6178v2, September 2011.

**2010**

** ****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.

**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.

**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. Also, in O. Goldreich, editor, *Property Testing - Current Research and Surveys*, volume 6390 of *Lecture Notes in Computer Science*, pages 341-345, January 2010.

**External Sampling,** by Andoni, A., Indyk, P., Onak, K, and Rubinfeld, R.
O. Goldreich, editor, *Property Testing - Current Research and Surveys,* volume 6390 of *Lecture Notes in Computer Science*, pages 240-243, January 2010. Earlier version 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.

**A local decision test for sparse polynomials,** by Grigorescu, E., Jung, K., and Rubinfeld, R.
*Information Processing Letters,* 110(20):898-901, 2010.

**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 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) TR07-128, December 2007.

**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 monotonicity of distributions over general partial orders,** by Bhattacharyya, A., Fischer, E., Rubinfeld, R., and Valiant, P. Electronic Colloquium on Computational Complexity (ECCC) TR10-027, February 2010.

**2009**

**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.

**Testing halfspaces,** by Matulef, K., O'Donnell, R., Rubinfeld, R., and Servedio, R. *Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)*, pages 256-264, New York, NY, January 4-6, 2009.
Also, Electronic Colloquium on Computational Complexity (ECCC) TR07-128, December 2007.

**Testing monotone high-dimensional distributions,** by Rubinfeld, R. and Servedio, R. *Random Structures and Algorithms,* 34(1):24-44, 2009. Earlier version in *Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005)*, pages 147-156, Baltimore, MD, May 2005.

**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.

**Sublinear Time Algorithms for Earth Mover's Distance,** Do Ba, K., Nguyen, H.L., Nguyen, H.N.,and Rubinfeld, R. CoRR abs/0904.0292v1, April 2009.

**2008**

**
Linearity Testing/Testing Hadamard Codes,** by Ronitt Rubinfeld.
*Encyclopedia of Algorithms*, Springer, 2008.

**Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions,** by Ben-Or, M., Coppersmith, D., Luby, M., and Rubinfeld, R. *Random Structures and Algorithms*, 32(1):49-70, 2008. Earlier version 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), TR04-052, June 2004.

**2007**

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

**Testing halfspaces,** by Matulef, K., O'Donnell, R., Rubinfeld, R., and Servedio, R.
Electronic Colloquium on Computational Complexity (ECCC) TR07-128, December 2007.

**2006**

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

**2005**

**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.

**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 versions in *Proceedings of the 34th ACM Symposium on Theory of Computing (STOC 2002)*, pages 678-687, Montreal, Canada, May 2002 and *Proceedings of the 17th IEEE Annual Conference on Computational Complexity*, Montreal, Quebec, 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) TR05-125, November 2005.

**2004**

**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) TR04-052, June 2004.

**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 (titled "Fast Approximate PCPs").

**Tolerant property testing and distance approximation,** by Parnas, M., Ron, D., and Rubinfeld, R. Electronic Colloquium on Computational Complexity (ECCC) TR04-010, February 2004.

**2003**

**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 (titled "Testing Parenthesis Languages.")

**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.

**Sublinear-time approximation of Euclidean minimum spanning tree,** by Czumaj, A., Ergun, F., Fortnow, L., Magen, A., Newman, I., Rubinfeld, R., and Sohler, C., *Proceedings of the 14th Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA 2003)*, pages 813-822, Baltimore, MD, January 2003.

**2002**

**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.

**The complexity of approximating entropy,** by Batu, T., Dasgupta, S., Kumar, R., and Rubinfeld, R. *Proceedings of the 34th ACM Symposium on Theory of Computing (STOC 2002)*, pages 678-687, Montreal, Canada, May 2002 and in joint session with *Proceedings of the 17th IEEE Annual Conference on Computational Complexity*, Montreal, Quebec, Canada, May 2002.

**On Testing Convexity and Submodularity, ** by Parnas, M., Ron, D., and Rubinfeld, R., 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.

**2001**

**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. Earlier version in
*Proceedings of the 37th IEEE Conference on Foundations of Computer Science (FOCS 1996)*, pages 592-601, Burlington, Vermont, October 1996 (titled ``Approximate Checking of Polynomials and Functional Equations (Extended Abstract))''.

**Approximating the minimum spanning tree weight in sublinear time,** by Chazelle, B., Rubinfeld, R., and Trevisan, L., 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.

**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 Parenthesis Languages,** by Parnas, M., Ron, D., and Rubinfeld, R., 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.

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

**Random Walks with Back Buttons,**** ** by Fagin, R., Karlin, A., Kleinber, J., Raghavan, P.,
Rajagopalan, S., Rubinfeld, R., Sudan, M., and Tomkins, A., *Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC 2000)*, pages 315-324, Portland, OR, May 2000.

**1999**

**Runtime Verification of Remotely Executed Code using Probabilistically Checkable Proof Systems,** by Batu, T., Rubinfeld, R., and White, P.
*FLoC Workshop on Run-Time Result Verification*, 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.

**Fast Approximate PCPs for Multidimensional Bin-packing Problems,** by Batu, T., Rubinfeld, R., and White, P. 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.

**Fast Approximate PCPs,**** ** by Ergun, F., Kumar, S. Ravi, and Rubinfeld, R., *Proceedings of the 31st ACM Symposium on Theory of Computing (STOC 1999)*, pages 41-50, Atlanta, GA, May 1999.

**1998**

**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.

**Spot Checkers,** by Ergun, F., Kannan, S., Kumar, R., Rubinfeld, R., and Vishwanathan, M., *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. Electronic Colloquium on Computational Complexity (ECCC) TR98-060, October 1998. Preliminary abstract in *Proceedings of the 36th IEEE Conference on Foundations of Computer Science (FOCS 1995)*, pages 294-303, Milwaukee, WI, October 1995.

**1997**

**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.

**1996**

**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. Also, ICSI Technical Report TR-90-040, August, 1990.

**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. Also, Technical Report TR-93-1387, Cornell University, Department of Computer Science, Ithaca, NY, September 1993.

** Approximate Checking of Polynomials and Functional Equations (Extended Abstract),** by Ergun, F., Kumar, S. Ravi, and Rubinfeld, R., *Proceedings of the 37th IEEE Conference on Foundations of Computer Science (FOCS 1996)*, pages 592-601, Burlington, Vermont, October 1996.

**1995**

**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 (titled "Learning Fallible Finite State Automata.")

**Learning polynomials with queries: the highly noisy case,**
by Goldreich, O., Rubinfeld, R., and Sudan, M., *Proceedings of the 36th IEEE Conference on Foundations of Computer Science (FOCS 1995)*, pages 294-303, Milwaukee, WI, October 1995.

**Exactly Learning Automata with Small Cover Time,** by Ron, D. and Rubinfeld, R., *Proceedings of the 8th Annual ACM Workshop on Computational Learning Theory (COLT)*, pages 427-436, Santa Cruz, CA, 1995.

**1994**

**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.,
in 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, Technical Report 93--1326, Cornell University, Department of Computer Science, Ithaca, NY, January 1993.

**On the Robustness of Functional Equations,** by Rubinfeld, R., *Proceedings of the 35th IEEE Conference
on Foundations of Computer Science (FOCS 1994)*,
pages 288-299, Santa Fe, New Mexico, November 1994.

**Robust Functional Equations with Applications to Self-Testing/Correcting**, by Rubinfeld, R., Technical Report 94-1435, Cornell University, Department of Computer Science, Ithaca, NY, July, 1994.

**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*). Also, ICSI Technical Report TR-91-062, November 1991. (Revised Version). Preliminary Abstract in *Proceedings of the 22nd ACM Symposium on Theory of Computing (STOC 1990)*, pages 73--83, Baltimore, MD, May 1990.

**Efficient Learning of Typical Finite Automata from Random Walks, **by Freund, Y., Kearns, M., Ron, D., Rubinfeld, R., Schapire, R., and Sellie, L., *Proceedings of the 25th ACM Symposium on Theory of Computing (STOC 1993)*, pages 315-324, San Diego, CA, May 1993. Preliminary Abstract.

**Learning Fallible Finite State Automata,** by Ron, D., and Rubinfeld, R., *Proceedings of the 6th Annual ACM Workshop on Computational Learning Theory (COLT 1993)*, pages 218-227, Santa Cruz, CA, July 1993.

**A New Modular Interpolation Algorithm for Factoring Multivariate Polynomials,** by Rubinfeld, R., and Zippel, R.
L. Adleman and M-D. Huang, Technical Report 93--1326, Cornell University, Department of Computer Science, Ithaca, NY, January 1993.

**Robust Characterizations of Polynomials with Applications to
Program Testing,** by Rubinfeld, R., and Sudan, M.
Technical Report TR-93-1387, Cornell University, Department of Computer Science, Ithaca, NY, September 1993.

**1992**

**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.
Also, 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.

**Reconstructing Algebraic Functions from Mixed Data,** by Ar, S., Lipton, R., Rubinfeld, R., and Sudan, M., *Proceedings of the 33rd IEEE Conference
on Foundations of Computer Science (FOCS 1992)*, pages 503-512, Pittsburgh, PA, October 1992.

**1991**

**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.

** ****Self-Testing/Correcting with Applications to Numerical Problems,** by Blum, M., Luby, M., and Rubinfeld, R.
ICSI Technical Report TR-91-062, November 1991 (Revised Version). Preliminary Abstract in *Proceedings of the 22nd ACM Symposium on Theory of Computing (STOC 1990)*, pages 73--83, Baltimore, MD, May 1990.

**1990**

**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. Also,
ICSI Technical Report No. TR-90-054, October 1990.

** Self-Testing/Correcting with Applications to Numerical Problems,** by Blum, M., Luby, M., and Rubinfeld, R., *Proceedings of the 22nd ACM Symposium on Theory of Computing (STOC 1990)*, pages 73--83, Baltimore, MD, May 1990. Prelminary Abstract.

**Designing Checkers for Programs that Run in Parallel,**
by Rubinfeld, R. ICSI Technical Report TR-90-040, August, 1990.

**1989**

** 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.

**1988**

**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., Technical Report CSD-88-434, University of California-Berkeley, June 1988.

**1987**

**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.