Ronitt Rubinfeld: Papers - Bibliographic Information

2024
  • Average-Case Local Computation Algorithms, Biswas, Amartya Shankha, Cao, Ruidi, Pyne, Edward, Rubinfeld, Ronitt, submitted for publication. Also, arXiv:2403.00129, March 2024.

    2023

  • New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling, Compton, Spencer, Mitrovic, Slobodan, Rubinfeld, Ronitt, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, Paderborn, Germany, July 2023.
  • Testing Distributional Assumptions of Learning Algorithms, Rubinfeld, R., Vasilyan, A., 55th Annual ACM Symposium on Theory of Computing (STOC 2023), Orlando, Florida, June 2023. Also, arxiv:2204.07196, November 2022.
  • Testing Tail Weight of a Distribution Via Hazard Rate, Aliakbarpour, M., Biswas, A.S., Ravichandran, K., Rubinfeld, R., International Conference on Algorithmic Learning Theory (ALT 2023), Singapore, pages 34-81, February 2023.
  • From Big Data Theory to Big Data Practice, Farach-Colton, M., Kuhn, D. K., Rubinfeld, R., Uznanski, P., (Dagstuhl Seminar 23071), Dagstuhl Reports 13(2):33-46, 2023.

    2022

  • Massively Parallel Algorithms for Small Subgraph Counting, Biswas, A.S., Eden, T., Liu, Q.C., Rubinfeld, R., Mitrovic, S., APPROX/RANDOM 2022, (Virtual), September 2022. Earlier version in arXiv:2002.08299, February 2020.
  • Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks, Aamand, A., Chen, J.Y. Indyk, P., Narayanan, S., Rubinfeld, R., Schiefer, N., Silwal, S., Wagner, T., NeurIPS 2022,, New Orleans, Louisiana, November 2022. Also, arXiv:2211.03232, November 2022.
  • Properly learning monotone functions via local reconstruction, Lange, Jane, Rubinfeld, Ronitt, Vasilyan, Arsen, 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022), Denver Colorado, October 2022. Also, arXiv: 2204.11894, April 2022.
  • Online Page Migration with ML Advice, Indyk, P., Mallmann-Trenn, F., Mitrovic, S., Rubinfeld, R., 25th International Conference on Artificial Intelligence and Statistics (AISTATS 2022), March 2022.

  • Triangle and Four Cycle Counting with Predictions in Graph Streams, Chen, J., Eden, T., Indyk, P., Lin, H., Narayanan, S., Rubinfeld, R., Silwal, S., Wagner, T., Woodruff, D., Zhang, M., Tenth International Conference on Learning Representations (ICLR 2022), April 2022. Also, CoRR abs/2203.09572, March 2022.
  • Local Access to Random Walks, Biswas, A.S., Pyne, Edward, Rubinfeld, R., Innovations in Theoretical Computer Science (ITCS 2022), January 2022.
  • Testing distributional assumptions of learning algorithms, Rubinfeld, R., Vasilyan, A., CoRR abs/2204.07196, November 2022.
  • Properly learning monotone functions via local reconstruction, Lange, J., Rubinfeld, R., Vasilyan, A., CoRR abs/2204.11894, April 2022.

    2021

  • Sampling Multiple Edges Efficiently, Eden, T., Mossel, S., Rubinfeld, R., RANDOM 2021, August 2021.
  • Decomposition-Optimal Algorithms for Counting and Sampling Arbitrary Subgraphs in Sublinear Time, Biswas, A. S., Eden T., and Rubinfeld, R., RANDOM 2021, August 2021.
  • Learning-based Support Estimation in Sublinear Time, Eden, T., Indyk, P., Narayanan, S., Rubinfeld, R., Silwal, S., Wagner, T., 9th International Conference on Learning Representations (ICLR 2021), May 2021.
  • Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees, Macke, S., Aliakbarpour, M., Diakonikolas, I., Parameswaran, A., Rubinfeld, R., ICDE 2021: 37th IEEE International Conference on Data Engineering, April 2021. Also, arXiv:2008.03891
  • Local Access to Random Walks, Biswas, A.S., Pyne, E., Rubinfeld, R., CoRR abs/2102.07740, February 2021.
  • Learning-based Support Estimation in Sublinear Time, Eden, T., Indyk, P., Narayanan, S., Rubinfeld, R., Silwal, S., Wagner, T., CoRR abs/2106.08396, 2021.
  • Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time, Biswas, A. S., Eden, T., Rubinfeld, R., CoRR abs/2107.06582, 2021.

    2020

  • New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling, Compton, S., Mitrovic, A., Rubinfeld, R., CoRR abs/2012.15002, December 2020.
  • Amortized Edge Sampling, Eden, T., Mossel, S., Rubinfeld, R., CoRR abs/2008.08032, August 2020.
  • Online Page Migration with ML Advice, Indyk, P., Mallmann-Trenn, F., Mitrovic, S., Rubinfeld, R., CoRR abs/2006.05028, June 2020.
  • Testing Tail Weight of a Distribution Via Hazard Rate, Aliakbarpour, M., Biswas, A.S., Ravichandran, Kavya, Rubinfeld, R. arXiv:2010.02888, 2020.
  • Local Algorithms for Sparse Spanning Graphs, Levi, R., Ron, D., Rubinfeld, R., Algorithmica, 82(4):747-786, 2020. Earlier version in APPROX/RANDOM 2014, and arXiv:1402.3609, 2014.
  • Local Access to Huge Random Objects through Partial Sampling, Biswas, A. S., Rubinfeld, R., Yodpinyanee, A., 11th Innovations in Theoretical Computer Science (ITCS 2020), Seattle, Washington, January 2020. Also, arXiv 1711.10692v2, January 2020.
  • Monotone probability distributions over the Boolean cube can be learned with sublinear samples, Rubinfeld, R., Vasilyan, A., 11th Innovations in Theoretical Computer Science (ITCS 2020), Seattle, Washington, January 2020. Also, arXiv:2002.03415, February 2020.
  • Improved Local Computation Algorithm for Set Cover via Sparsification, Grunau, C., Mitrovic, S., Rubinfeld, R., Vakilian, A., ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, Utah, January 2020. Also, arXiv:1910.14154, October 2019.
  • Massively Parallel Algorithms for Small Subgraph Counting, Biswas, A. S., Eden, T., Liu, Q. C., Mitrovic, S., Rubinfeld, R. arXiv:2002.08299, February 2020.
  • Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees, Macke, S., Aliakbarpour, M., Diakonikolas, I., Parameswaran, A., Rubinfeld, R., arXiv:2008.03891, August 2020.

    2019

  • Private Testing of Distributions via Sample Permutations, Aliakbarpour, A., Diakonikolas, I., Kane, D., Rubinfeld, R., Thirty-third Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada, December 2019.
  • Improved Local Computation Algorithm for Set Cover via Sparsification, Grunau, C., Mitrovic, S., Rubinfeld, R., Vakilian, A., arXiv:1910.14154, October 2019.
  • Approximating the noise sensitivity of a monotone Boolean function, Rubinfeld, R., Vasilyan, A., International Conference on Randomization and Computation (RANDOM 2019), Cambridge, MA, September 2019. Also, arXiv:1904.06745, April 2019.
  • Towards Testing Monotonicity of Distributions Over General Posets, Alaikbarpour, A., Gouleakis, T., Peebles, J., Rubinfeld, R., Yodpinyanee, A., Proceedings of the Thirty-Second Conference on Learning Theory (COLT 2019), volume 99 of Proceedings of Machine Learning Research, Phoenix, AZ, pages 34-82, June 2019. Also, arXiv:1907.03182, 2019.
  • Testing Mixtures of Discrete Distributions, Aliakbarpour, M., Kumar, R., Rubinfeld, R., Proceedings of the Thirty-Second Conference on Learning Theory (COLT 2019), volume 99 of Proceedings of Machine Learning Research, Phoenix, AZ, pages 83-114, June 2019. Also, arXiv:1907.03190, 2019.
  • Local Computation Algorithms for Spanners, Parter, M., Rubinfeld, R., Vakilian, A., Yodpinyanee, A., Innovations in Theoretical Computer Science (ITCS), San Diego, CA, January 2019. Also, arXiv:1902.08266, 2019.
  • Set Cover in Sub-linear Time, Indyk, P., Mahabadi, S., Rubinfeld, R., Vakilian, A., Yodpinyanee, A. arXiv:1902.03534, 2019. Also, in SODA 2018.

    2018

  • Sampling Correctors, Canonne, C.L., Gouleakis, T., Rubinfeld, R., SIAM Journal on Computing, 47(4):1373-1423, 2018. Earlier version in Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, pages 93-102, January 2016. Also, arXiv:1504.06544, April 2015.
  • Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling, Aliakbarpour, A., Biswas, A.S., Gouleakis, T., Peebles, J., Rubinfeld, R., Yodpinyanee, A., Algorithmica, 80(2):668-697, 2018.
  • Testing Shape Restrictions of Discrete Distributions, Canonne, C.L., Diakonikolas, I., Gouleakis, T., Rubinfeld, R., Theory Comput. Syst., 62(1):4-62, 2018. Earlier version in 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, Orléans, France, pages 25:1-25:14, February 2016. Also, arXiv:1507.03558, 2015.
  • Differentially Private Identity and Equivalence Testing of Discrete Distributions, Aliakbarpour, M., Diakonikolas, I., Rubinfeld, R., Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, pages 169-178, July 2018.
  • Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover, Ghaffari, M., Gouleakis, T., Konrad, C., Mitrovic, S., Rubinfeld, R., Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, pages 129-138, July 2018. Also, arXiv.1802.08237, February 2018.
  • Set Cover in Sub-linear Time, Indyk, P., Mahabadi, S., Rubinfeld, R., Vakilian, A., Yodpinyanee, A., Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, pages 2467-2486, January 2018. Also, arXiv:1902.03534, February 2019.

    2017

  • Local Computation Local Computation Algorithms for Graphs of Non-constant Degrees, Levi, R., Rubinfeld, R., Yodpinyanee, A., Algorithmica,77(4):971-994, 2017. Earlier version in Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, pages 59-61, Portland, Oregon, June 2015. Also, arXiv:1502.04022, 2015.
  • I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making, Rahman, S., Aliakbarpour, M., Kong, H., Blais, E., Karahalios, K., Parameswaran, Ronitt Rubinfeld, R., Proceedings of the VLDB Endowment, 10(11):1262-1273, 2017.
  • Constructing near spanning trees with few local inspections, Levi, R., Moshkovitz, G., Ron, D., Rubinfeld, R., Shapira, A., Random Struct. Algorithms, 50(2):183-200, 2017. Also, Electronic Colloquium on Computational Complexity (ECCC) TR15-019, February 2015 and arXiv:1502.00413, 2015.
  • Fractional Set Cover in the Streaming Model, Indyk, I., Mahabadi, S., Rubinfeld, R., Ullman, J., Vakilian, A., Yodpinyanee, A., Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, Berkeley, CA, pages 12:1-12:20, August 2017.
  • Can We Locally Compute Sparse Connected Subgraphs?, Rubinfeld, R.. In Pascal Weil, editor, Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 2017, volume 10304 of Lecture Notes in Computer Science, pages 38-47, Springer, 2017.
  • Differentially Private Identity and Closeness Testing of Discrete Distributions, Aliakbarpour, M., Diakonikolas, I., Rubinfeld, R., arXiv:1707.05497, July 2017.
  • Local-Access Generators for Basic Random Graph Models, Biswas, A.S., Rubinfeld, R., Yodpinyanee, A., arXiv:1711.10692, November 2017.

    2016

  • 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, 59(1):99-111,2016. Also, arXiv:1412.5484, 2014.
  • A Local Algorithm for Constructing Spanners in Minor-Free Graphs, Levi, R., Ron, D., Rubinfeld, R., Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, Paris, France, pages 38:1-38:15, September 2016. Also, arXiv:1604.07038, 2016.
  • Learning and Testing Junta Distributions, Aliakbarpour, M., Blais, E., Rubinfeld, R., Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, pages 19-46, June 2016.
  • Sampling Correctors, Canonne, C.L., Gouleakis, T., Rubinfeld, R., Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS 2016), Cambridge, MA, pages 93-102, January 2016. Also, arXiv:1504.06544, April 2015.
  • Testing Shape Restrictions of Discrete Distributions, Canonne, C.L., Diakonikolas, I., Gouleakis, T., Rubinfeld, R., 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, Orléans, France, pages 25:1-25:14, February 2016. Also, arXiv:1507.03558, 2015.
  • Something for (Almost) Nothing: New Advances in Sublinear-Time Algorithms, Rubinfeld, R., Blais, E., Handbook of Big Data, pages 155-167, 2016.
  • Linearity Testing/Testing Hadamard Codes, Raskhodnikova, S., Rubinfeld, R., Encyclopedia of Algorithms, pages 1107-1110, 2016.
  • Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation, Aliakbarpour, M., Biswas, A.S., Gouleakis, T., Peebles, J., Rubinfeld, R., Yodpinyanee, A., arXiv:1601.04233, 2016.

    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, arXiv: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, arXiv:1412.3040, 2014.
  • Erratum for: Approximating and Testing k-Histogram Distributions in Sub-linear Time, Indyk, P., Levi, R., Rubinfeld, R., Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia, May 31 - June 4, 2015.
  • 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, arXiv:1502.00413, 2015.
  • Sampling Correctors, Canonne, C.L., Gouleakis, T., Rubinfeld, R., arXiv:1504.06544, April 2015.
  • Testing Shape Restrictions of Discrete Distributions, by Canonne, C. L., Diakonikolas, I., Gouleakis, T., and Rubinfeld, R. arXiv: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., arXiv: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, arXiv: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 arXiv: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. arXiv: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, arXiv: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, arXiv: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, arXiv: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, arXiv: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, arXiv: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, arXiv: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, arXiv:1109.6178v2, September 2011.
  • Local reconstructors and tolerant testers for connectivity and diameter, by Campagna, A., Guo, A., and Rubinfeld, R. arXiv: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, arXiv: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, arXiv: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, arXiv: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. arXiv:1110.1079v1, October 2011.
  • Space-efficient Local Computation Algorithms, by Alon, N., Rubinfeld, R., Vardi, S., and Xie, N. arXiv: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. In 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. arXiv: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. arXiv: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, arXiv: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., Rubinfeld, R., and Samorodnitsky, A. 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. 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.
    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.

    Accessibility