Ronitt Rubinfeld

Professor

Former affiliation
1989 …2023

Research activity per year

Filter
Conference contribution

Search results

  • 2023

    New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling

    Compton, S., Mitrović, S. & Rubinfeld, R., Jul 2023, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023. Etessami, K., Feige, U. & Puppis, G. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 45. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 261).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Testing Distributional Assumptions of Learning Algorithms

    Rubinfeld, R. & Vasilyan, A., 2 Jun 2023, STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Saha, B. & Servedio, R. A. (eds.). Association for Computing Machinery, p. 1643-1656 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    3 Scopus citations
  • 2022

    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., 2022, Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022. Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K. & Oh, A. (eds.). Neural information processing systems foundation, (Advances in Neural Information Processing Systems; vol. 35).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    5 Scopus citations
  • Local Access to Random Walks

    Biswas, A. S., Pyne, E. & Rubinfeld, R., 1 Jan 2022, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022. Braverman, M. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 24. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 215).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    1 Scopus citations
  • Massively Parallel Algorithms for Small Subgraph Counting

    Biswas, A. S., Eden, T., Liu, Q. C., Rubinfeld, R. & Mitrović, S., 1 Sep 2022, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022. Chakrabarti, A. & Swamy, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 39. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 245).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    1 Scopus citations
  • Properly learning monotone functions via local correction

    Lange, J., Rubinfeld, R. & Vasilyan, A., 2022, Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022. IEEE Computer Society, p. 75-86 12 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2022-October).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    2 Scopus citations
  • 2021

    Rapid approximate aggregation with distribution-sensitive interval guarantees

    Macke, S., Aliakbarpour, M., Diakonikolas, I., Parameswaran, A. & Rubinfeld, R., Apr 2021, Proceedings - 2021 IEEE 37th International Conference on Data Engineering, ICDE 2021. IEEE Computer Society, p. 1703-1714 12 p. 9458639. (Proceedings - International Conference on Data Engineering; vol. 2021-April).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
  • Sampling multiple edges efficiently

    Eden, T., Mossel, S. & Rubinfeld, R., 1 Sep 2021, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021. Wootters, M. & Sanita, L. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 51. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 207).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    6 Scopus citations
  • Towards a decomposition-optimal algorithm for counting and sampling arbitrary motifs in sublinear time

    Biswas, A. S., Eden, T. & Rubinfeld, R., 1 Sep 2021, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021. Wootters, M. & Sanita, L. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 55. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 207).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    4 Scopus citations
  • 2020

    Improved local computation algorithm for set cover via sparsification

    Grunau, C., Mitrović, S., Rubinfeld, R. & Vakilian, A., 2020, 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Chawla, S. (ed.). Association for Computing Machinery, p. 2993-3011 19 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2020-January).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    8 Scopus citations
  • Local access to huge random objects through partial sampling

    Biswas, A. S., Rubinfeld, R. & Yodpinyanee, A., Jan 2020, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020. Vidick, T. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 27. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 151).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    4 Scopus citations
  • Monotone probability distributions over the Boolean cube can be learned with sublinear samples

    Rubinfeld, R. & Vasilyan, A., Jan 2020, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020. Vidick, T. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 28. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 151).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    2 Scopus citations
  • 2019

    Approximating the noise sensitivity of a monotone Boolean function

    Rubinfeld, R. & Vasilyan, A., Sep 2019, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019. Achlioptas, D. & Vegh, L. A. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 52. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 145).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    2 Scopus citations
  • Local computation algorithms for spanners

    Parter, M., Rubinfeld, R., Vakilian, A. & Yodpinyanee, A., 1 Jan 2019, 10th Innovations in Theoretical Computer Science, ITCS 2019. Blum, A. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 58. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 124).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    13 Scopus citations
  • 2018

    Differentially private identity and equivalence testing of discrete distributions

    Aliakbarpour, M., Diakonikolas, I. & Rubinfeld, R., 2018, 35th International Conference on Machine Learning, ICML 2018. Krause, A. & Dy, J. (eds.). International Machine Learning Society (IMLS), p. 266-283 18 p. (35th International Conference on Machine Learning, ICML 2018; vol. 80).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    14 Scopus citations
  • Improved massively parallel computation algorithms for MIS, matching, and vertex cover

    Ghaffari, M., Gouleakis, T., Konrad, C., Mitrović, S. & Rubinfeld, R., 23 Jul 2018, PODC 2018 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, p. 129-138 10 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    80 Scopus citations
  • Set cover in sub-linear time

    Indyk, P., Mahabadi, S., Rubinfeld, R., Vakilian, A. & Yodpinyanee, A., 2018, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Czumaj, A. (ed.). Association for Computing Machinery, p. 2467-2486 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    8 Scopus citations
  • 2017

    Can we locally compute sparse connected subgraphs?

    Rubinfeld, R., 2017, Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings. Weil, P. (ed.). Springer Verlag, p. 38-47 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10304 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    2 Scopus citations
  • Fractional set cover in the streaming model

    Indyk, P., Mahabadi, S., Rubinfeld, R., Ullman, J., Vakilian, A. & Yodpinyanee, A., 1 Aug 2017, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 20th International Workshop, APPROX 2017 and 21st International Workshop, RANDOM 2017. Rolim, J. D. P., Jansen, K., Williamson, D. P. & Vempala, S. S. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 12. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 81).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    14 Scopus citations
  • 2016

    A local algorithm for constructing spanners in minor-free graphs

    Levi, R., Ron, D. & Rubinfeld, R., 1 Sep 2016, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016. Jansen, K., Mathieu, C., Rolim, J. D. P. & Umans, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 60).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    6 Scopus citations
  • Sampling correctors

    Canonne, C. L., Gouleakis, T. & Rubinfeld, R., 14 Jan 2016, ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery, Inc, p. 93-102 10 p. (ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    4 Scopus citations
  • Testing shape restrictions of discrete distributions

    Canonne, C. L., Diakonikolas, I., Gouleakis, T. & Rubinfeld, R., 1 Feb 2016, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016. Vollmer, H. & Ollinger, N. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 25. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 47).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    13 Scopus citations
  • 2015

    Brief announcement: Local computation algorithms for graphs of non-constant degrees

    Levi, R., Rubinfeld, R. & Yodpinyanee, A., 13 Jun 2015, SPAA 2015 - Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, p. 59-61 3 p. (Annual ACM Symposium on Parallelism in Algorithms and Architectures; vol. 2015-June).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    11 Scopus citations
  • 2014

    Local algorithms for sparse spanning graphs

    Levi, R., Ron, D. & Rubinfeld, R., 1 Sep 2014, Leibniz International Proceedings in Informatics, LIPIcs. Jansen, K., Moore, C., Devanur, N. R. & Rolim, J. D. P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 826-842 17 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 28).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    19 Scopus citations
  • Testing probability distributions underlying aggregated data

    Canonne, C. & Rubinfeld, R., 2014, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer Verlag, p. 283-295 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8572 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    30 Scopus citations
  • 2013

    A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support

    Dutta, A., Levi, R., Ron, D. & Rubinfeld, R., 2013, Proceedings - DCC 2013: 2013 Data Compression Conference. p. 113-122 10 p. 6543047. (Data Compression Conference Proceedings).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    12 Scopus citations
  • Local reconstructors and tolerant testers for connectivity and diameter

    Campagna, A., Guo, A. & Rubinfeld, R., 2013, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings. p. 411-424 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8096 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    25 Scopus citations
  • 2012

    A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size

    Onak, K., Ron, D., Rosen, M. & Rubinfeld, R., 2012, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Association for Computing Machinery, p. 1123-1131 9 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    65 Scopus citations
  • Approximating and testing k-histogram distributions in sub-linear time

    Indyk, P., Levi, R. & Rubinfeld, R., 2012, PODS '12 - Proceedings of the 31st Symposium on Principles of Database Systems. p. 15-21 7 p. (Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    42 Scopus citations
  • Space-efficient local computation algorithms

    Alon, N., Rubinfeld, R., Vardi, S. & Xie, N., 2012, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Association for Computing Machinery, p. 1132-1139 8 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    77 Scopus citations
  • Testing similar means

    Levi, R., Ron, D. & Rubinfeld, R., 2012, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 1 ed. p. 629-640 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7391 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • 2011

    Approximating the influence of monotone boolean functions in O(√n) query complexity

    Ron, D., Rubinfeld, R., Safra, M. & Weinstein, O., 2011, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings. p. 664-675 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6845 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    7 Scopus citations
  • Testing Properties of Collections of Distributions.

    Levi, R., Ron, D. & Rubinfeld, R., 1 Jan 2011, Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS). Vol. 17. p. 179-194 16 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • 2010

    Dynamic approximate vertex cover and maximum matching

    Onak, K. & Rubinfeld, R., 2010, Property Testing - Current Research and Surveys. p. 341-345 5 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6390 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    3 Scopus citations
  • Improved recommendations via (More) collaboration

    Boim, R., Kaplan, H., Milo, T. & Rubinfeld, R., 2010, Proceedings of the 13th International Workshop on the Web and Databases, WebDB 2010, Co-located with ACM SIGMOD 2010. Association for Computing Machinery, 12. (Proceedings of the ACM SIGMOD International Conference on Management of Data).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
  • Maintaining a large matching and a small vertex cover

    Onak, K. & Rubinfeld, R., 2010, STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing. p. 457-464 8 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    88 Scopus citations
  • Sublinear algorithms in the external memory model

    Andoni, A., Indyk, P., Onak, K. & Rubinfeld, R., 2010, Property Testing - Current Research and Surveys. p. 240-243 4 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6390 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
  • Testing (subclasses of) halfspaces

    Matulef, K., O'Donnell, R., Rubinfeld, R. & Servedio, R., 2010, Property Testing - Current Research and Surveys. p. 334-340 7 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6390 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    2 Scopus citations
  • Testing non-uniform k-wise independent distributions over product spaces

    Rubinfeld, R. & Xie, N., 2010, Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1 ed. p. 565-581 17 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6198 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    6 Scopus citations
  • 2009

    External sampling

    Andoni, A., Indyk, P., Onak, K. & Rubinfeld, R., 2009, Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings. PART 1 ed. p. 83-94 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5555 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    4 Scopus citations
  • Testing ±1-weight halfspace

    Matulef, K., O'Donnell, R., Rubinfeld, R. & Servedio, R. A., 2009, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. p. 646-657 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5687 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    24 Scopus citations
  • Testing halfspaces

    Matulef, K., O'Donnell, R., Rubinfeld, R. & Servedio, R. A., 2009, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery, p. 256-264 9 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    21 Scopus citations
  • 2007

    Sublinear algorithms for approximating string compressibility

    Raskhodnikova, S., Ron, D., Rubinfeld, R. & Smith, A., 2007, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings. Springer Verlag, p. 609-623 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4627 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    4 Scopus citations
  • Testing for concise representations

    Diakonikolas, I., Lee, H. K., Matulef, K., Onak, K., Rubinfeld, R., Servedio, R. A. & Wan, A., 2007, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007. p. 549-558 10 p. 4389524. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    75 Scopus citations
  • Testing k-wise and almost k-wise independence

    Alon, N., Andoni, A., Kaufman, T., Matulef, K., Rubinfeld, R. & Xie, N., 2007, STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. p. 496-505 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    86 Scopus citations
  • 2002

    On testing convexity and submodularity

    Parnas, M., Ron, D. & Rubinfeld, R., 2002, Randomization and Approximation Techniques in Computer Science - 6th International Workshop, RANDOM 2002, Proceedings. Vadhan, S. & Rolim, J. D. P. (eds.). Springer Verlag, p. 11-25 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2483).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    1 Scopus citations
  • 2001

    Approximating the minimum spanning tree weight in sublinear time

    Chazelle, B., Rubinfeld, R. & Trevisan, L., 2001, Automata, Languages and Programming - 28th International Colloquium, ICALP 2001, Proceedings. Orejas, F., Spirakis, P. G. & van Leeuwen, J. (eds.). Springer Verlag, p. 190-200 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2076 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    27 Scopus citations
  • Testing parenthesis languages

    Parnas, M., Ron, D. & Rubinfeld, R., 2001, 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, Proceedings. Goemans, M., Jansen, K., Rolim, J. D. P. & Trevisan, L. (eds.). Berlin Heidelberg: Springer Verlag, p. 261-272 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2129).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    8 Scopus citations
  • 2000

    Random walks with "back buttons" (extended abstract)

    Fagin, R., Karlin, A. R., Kleinberg, J., Raghavan, P., Rajagopalan, S., Rubinfeld, R., Sudan, M. & Tomkins, A., 2000, Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000. p. 484-493 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
    24 Scopus citations
  • 1999

    Fast approximate PCPs for multidimensional bin-packing problems

    Batu, T., Rubinfeld, R. & White, P., 1999, Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings. Rolim, J. D. P., Sinclair, A., Hochbaum, D. & Jansen, K. (eds.). Springer Verlag, p. 245-256 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1671).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    16 Scopus citations