default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDRonitt Rubinfeld
Person information
- affiliation: MIT, Cambridge, USA
- affiliation: Tel Aviv University, Blavatnik School of Computer Science, Israel
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j49]Spencer Compton, Slobodan Mitrovic, Ronitt Rubinfeld:
New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling. Algorithmica 86(9): 2997-3026 (2024)- [c94]Slobodan Mitrovic, Ronitt Rubinfeld, Mihir Singhal:
Locally Computing Edge Orientations. ESA 2024: 89:1-89:17 - [i62]Amartya Shankha Biswas, Ruidi Cao, Edward Pyne, Ronitt Rubinfeld:
Average-Case Local Computation Algorithms. CoRR abs/2403.00129 (2024) - [i61]Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Ronitt Rubinfeld:
Stochastic Matching via In-n-Out Local Computation Algorithms. CoRR abs/2411.08805 (2024) - [i60]Maryam Aliakbarpour, Piotr Indyk, Ronitt Rubinfeld, Sandeep Silwal:
Optimal Algorithms for Augmented Testing of Discrete Distributions. CoRR abs/2412.00974 (2024) - 2023
- [c93]Maryam Aliakbarpour, Amartya Shankha Biswas, Kavya Ravichandran, Ronitt Rubinfeld:
Testing Tail Weight of a Distribution Via Hazard Rate. ALT 2023: 34-81 - [c92]Spencer Compton, Slobodan Mitrovic, Ronitt Rubinfeld:
New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling. ICALP 2023: 45:1-45:16 - [c91]Ronitt Rubinfeld, Arsen Vasilyan:
Testing Distributional Assumptions of Learning Algorithms. STOC 2023: 1643-1656 - [i59]Martin Farach-Colton, Fabian Daniel Kuhn, Ronitt Rubinfeld, Przemyslaw Uznanski:
From Big Data Theory to Big Data Practice (Dagstuhl Seminar 23071). Dagstuhl Reports 13(2): 33-46 (2023) - 2022
- [c90]Piotr Indyk, Frederik Mallmann-Trenn, Slobodan Mitrovic, Ronitt Rubinfeld:
Online Page Migration with ML Advice. AISTATS 2022: 1655-1670 - [c89]Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Ronitt Rubinfeld, Slobodan Mitrovic:
Massively Parallel Algorithms for Small Subgraph Counting. APPROX/RANDOM 2022: 39:1-39:28 - [c88]Jane Lange, Ronitt Rubinfeld, Arsen Vasilyan:
Properly learning monotone functions via local correction. FOCS 2022: 75-86 - [c87]Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang:
Triangle and Four Cycle Counting with Predictions in Graph Streams. ICLR 2022 - [c86]Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld:
Local Access to Random Walks. ITCS 2022: 24:1-24:22 - [c85]Anders Aamand, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer, Sandeep Silwal, Tal Wagner:
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks. NeurIPS 2022 - [i58]Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang:
Triangle and Four Cycle Counting with Predictions in Graph Streams. CoRR abs/2203.09572 (2022) - [i57]Ronitt Rubinfeld, Arsen Vasilyan:
Testing distributional assumptions of learning algorithms. CoRR abs/2204.07196 (2022) - [i56]Jane Lange, Ronitt Rubinfeld, Arsen Vasilyan:
Properly learning monotone functions via local reconstruction. CoRR abs/2204.11894 (2022) - [i55]Anders Aamand, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer, Sandeep Silwal, Tal Wagner:
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks. CoRR abs/2211.03232 (2022) - 2021
- [c84]Talya Eden, Saleet Mossel, Ronitt Rubinfeld:
Sampling Multiple Edges Efficiently. APPROX-RANDOM 2021: 51:1-51:15 - [c83]Amartya Shankha Biswas, Talya Eden, Ronitt Rubinfeld:
Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time. APPROX-RANDOM 2021: 55:1-55:19 - [c82]Stephen Macke, Maryam Aliakbarpour
, Ilias Diakonikolas, Aditya G. Parameswaran, Ronitt Rubinfeld:
Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees. ICDE 2021: 1703-1714 - [c81]Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner:
Learning-based Support Estimation in Sublinear Time. ICLR 2021 - [i54]Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld:
Local Access to Random Walks. CoRR abs/2102.07740 (2021) - [i53]Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner:
Learning-based Support Estimation in Sublinear Time. CoRR abs/2106.08396 (2021) - [i52]Amartya Shankha Biswas, Talya Eden, Ronitt Rubinfeld:
Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time. CoRR abs/2107.06582 (2021) - 2020
- [j48]Reut Levi, Dana Ron, Ronitt Rubinfeld:
Local Algorithms for Sparse Spanning Graphs. Algorithmica 82(4): 747-786 (2020) - [c80]Amartya Shankha Biswas, Ronitt Rubinfeld, Anak Yodpinyanee:
Local Access to Huge Random Objects Through Partial Sampling. ITCS 2020: 27:1-27:65 - [c79]Ronitt Rubinfeld, Arsen Vasilyan:
Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples. ITCS 2020: 28:1-28:34 - [c78]Christoph Grunau, Slobodan Mitrovic, Ronitt Rubinfeld, Ali Vakilian:
Improved Local Computation Algorithm for Set Cover via Sparsification. SODA 2020: 2993-3011 - [i51]Ronitt Rubinfeld, Arsen Vasilyan:
Monotone probability distributions over the Boolean cube can be learned with sublinear samples. CoRR abs/2002.03415 (2020) - [i50]Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Slobodan Mitrovic, Ronitt Rubinfeld:
Parallel Algorithms for Small Subgraph Counting. CoRR abs/2002.08299 (2020) - [i49]Piotr Indyk, Frederik Mallmann-Trenn, Slobodan Mitrovic, Ronitt Rubinfeld:
Online Page Migration with ML Advice. CoRR abs/2006.05028 (2020) - [i48]Stephen Macke, Maryam Aliakbarpour, Ilias Diakonikolas, Aditya G. Parameswaran, Ronitt Rubinfeld:
Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees. CoRR abs/2008.03891 (2020) - [i47]Talya Eden, Saleet Mossel, Ronitt Rubinfeld:
Amortized Edge Sampling. CoRR abs/2008.08032 (2020) - [i46]Maryam Aliakbarpour, Amartya Shankha Biswas, Kavya Ravichandran, Ronitt Rubinfeld:
Testing Tail Weight of a Distribution Via Hazard Rate. CoRR abs/2010.02888 (2020) - [i45]Spencer Compton, Slobodan Mitrovic, Ronitt Rubinfeld:
New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling. CoRR abs/2012.15002 (2020)
2010 – 2019
- 2019
- [c77]Ronitt Rubinfeld, Arsen Vasilyan:
Approximating the Noise Sensitivity of a Monotone Boolean Function. APPROX-RANDOM 2019: 52:1-52:17 - [c76]Maryam Aliakbarpour, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee:
Towards Testing Monotonicity of Distributions Over General Posets. COLT 2019: 34-82 - [c75]Maryam Aliakbarpour, Ravi Kumar, Ronitt Rubinfeld:
Testing Mixtures of Discrete Distributions. COLT 2019: 83-114 - [c74]Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee:
Local Computation Algorithms for Spanners. ITCS 2019: 58:1-58:21 - [c73]Maryam Aliakbarpour, Ilias Diakonikolas, Daniel Kane, Ronitt Rubinfeld:
Private Testing of Distributions via Sample Permutations. NeurIPS 2019: 10877-10888 - [c72]Ronitt Rubinfeld:
Local Computation Algorithms. PODC 2019: 3 - [i44]Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee:
Set Cover in Sub-linear Time. CoRR abs/1902.03534 (2019) - [i43]Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee:
Local Computation Algorithms for Spanners. CoRR abs/1902.08266 (2019) - [i42]Ronitt Rubinfeld, Arsen Vasilyan:
Approximating the noise sensitivity of a monotone Boolean function. CoRR abs/1904.06745 (2019) - [i41]Maryam Aliakbarpour, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee:
Towards Testing Monotonicity of Distributions Over General Posets. CoRR abs/1907.03182 (2019) - [i40]Maryam Aliakbarpour, Ravi Kumar, Ronitt Rubinfeld:
Testing Mixtures of Discrete Distributions. CoRR abs/1907.03190 (2019) - [i39]Christoph Grunau, Slobodan Mitrovic, Ronitt Rubinfeld, Ali Vakilian:
Improved Local Computation Algorithm for Set Cover via Sparsification. CoRR abs/1910.14154 (2019) - 2018
- [j47]Maryam Aliakbarpour, Amartya Shankha Biswas, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee:
Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling. Algorithmica 80(2): 668-697 (2018) - [j46]Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, Ronitt Rubinfeld:
Testing Shape Restrictions of Discrete Distributions. Theory Comput. Syst. 62(1): 4-62 (2018) - [j45]Clément L. Canonne, Themis Gouleakis, Ronitt Rubinfeld:
Sampling Correctors. SIAM J. Comput. 47(4): 1373-1423 (2018) - [c71]Maryam Aliakbarpour, Ilias Diakonikolas, Ronitt Rubinfeld:
Differentially Private Identity and Equivalence Testing of Discrete Distributions. ICML 2018: 169-178 - [c70]Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, Ronitt Rubinfeld:
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover. PODC 2018: 129-138 - [c69]Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee:
Set Cover in Sub-linear Time. SODA 2018: 2467-2486 - [i38]Mohsen Ghaffari, Themis Gouleakis, Slobodan Mitrovic, Ronitt Rubinfeld:
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover. CoRR abs/1802.08237 (2018) - 2017
- [j44]Reut Levi, Ronitt Rubinfeld, Anak Yodpinyanee:
Local Computation Algorithms for Graphs of Non-constant Degrees. Algorithmica 77(4): 971-994 (2017) - [j43]Sajjadur Rahman, Maryam Aliakbarpour, Hidy Kong, Eric Blais, Karrie Karahalios, Aditya G. Parameswaran, Ronitt Rubinfeld:
I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making. Proc. VLDB Endow. 10(11): 1262-1273 (2017) - [j42]Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira:
Constructing near spanning trees with few local inspections. Random Struct. Algorithms 50(2): 183-200 (2017) - [c68]Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan R. Ullman, Ali Vakilian, Anak Yodpinyanee:
Fractional Set Cover in the Streaming Model. APPROX-RANDOM 2017: 12:1-12:20 - [c67]Ronitt Rubinfeld:
Can We Locally Compute Sparse Connected Subgraphs? CSR 2017: 38-47 - [c66]Ronitt Rubinfeld:
Local Computation Algorithms (Invited Talk). ICALP 2017: 3:1-3:1 - [i37]Maryam Aliakbarpour, Ilias Diakonikolas, Ronitt Rubinfeld:
Differentially Private Identity and Closeness Testing of Discrete Distributions. CoRR abs/1707.05497 (2017) - [i36]Amartya Shankha Biswas, Ronitt Rubinfeld, Anak Yodpinyanee:
Local-Access Generators for Basic Random Graph Models. CoRR abs/1711.10692 (2017) - 2016
- [j41]Sheela Devadas, Ronitt Rubinfeld:
A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness. Theory Comput. Syst. 59(1): 99-111 (2016) - [c65]Reut Levi, Dana Ron, Ronitt Rubinfeld:
A Local Algorithm for Constructing Spanners in Minor-Free Graphs. APPROX-RANDOM 2016: 38:1-38:15 - [c64]Maryam Aliakbarpour, Eric Blais, Ronitt Rubinfeld:
Learning and Testing Junta Distributions. COLT 2016: 19-46 - [c63]Clément L. Canonne, Themis Gouleakis, Ronitt Rubinfeld:
Sampling Correctors. ITCS 2016: 93-102 - [c62]Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, Ronitt Rubinfeld:
Testing Shape Restrictions of Discrete Distributions. STACS 2016: 25:1-25:14 - [p4]Ronitt Rubinfeld, Eric Blais:
Something for (Almost) Nothing: New Advances in Sublinear-Time Algorithms. Handbook of Big Data 2016: 155-167 - [r2]Sofya Raskhodnikova, Ronitt Rubinfeld:
Linearity Testing/Testing Hadamard Codes. Encyclopedia of Algorithms 2016: 1107-1110 - [i35]Maryam Aliakbarpour, Amartya Shankha Biswas, Themistoklis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee:
Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation. CoRR abs/1601.04233 (2016) - [i34]Reut Levi, Dana Ron, Ronitt Rubinfeld:
A Local Algorithm for Constructing Spanners in Minor-Free Graphs. CoRR abs/1604.07038 (2016) - 2015
- [j40]Albert Kim, Eric Blais, Aditya G. Parameswaran, Piotr Indyk, Samuel Madden, Ronitt Rubinfeld:
Rapid Sampling for Visualizations with Ordering Guarantees. Proc. VLDB Endow. 8(5): 521-532 (2015) - [c61]Piotr Indyk, Reut Levi, Ronitt Rubinfeld:
Erratum for: Approximating and Testing k-Histogram Distributions in Sub-linear Time. PODS 2015: 343 - [c60]Reut Levi, Ronitt Rubinfeld, Anak Yodpinyanee:
Brief Announcement: Local Computation Algorithms for Graphs of Non-Constant Degrees. SPAA 2015: 59-61 - [e4]Rocco A. Servedio, Ronitt Rubinfeld:
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015. ACM 2015, ISBN 978-1-4503-3536-2 [contents] - [i33]Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira:
Constructing Near Spanning Trees with Few Local Inspections. CoRR abs/1502.00413 (2015) - [i32]Reut Levi, Ronitt Rubinfeld, Anak Yodpinyanee:
Local Computation Algorithms for Graphs of Non-Constant Degrees. CoRR abs/1502.04022 (2015) - [i31]Clément L. Canonne, Themis Gouleakis, Ronitt Rubinfeld:
Sampling Correctors. CoRR abs/1504.06544 (2015) - [i30]Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, Ronitt Rubinfeld:
Testing Shape Restrictions of Discrete Distributions. CoRR abs/1507.03558 (2015) - [i29]Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira:
Constructing Near Spanning Trees with Few Local Inspections. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j39]Reut Levi, Dana Ron, Ronitt Rubinfeld:
Testing Similar Means. SIAM J. Discret. Math. 28(4): 1699-1724 (2014) - [c59]Reut Levi, Dana Ron, Ronitt Rubinfeld:
Local Algorithms for Sparse Spanning Graphs. APPROX-RANDOM 2014: 826-842 - [c58]Clément L. Canonne, Ronitt Rubinfeld:
Testing Probability Distributions Underlying Aggregated Data. ICALP (1) 2014: 283-295 - [i28]Reut Levi, Dana Ron, Ronitt Rubinfeld:
Local Algorithms for Sparse Spanning Graphs. CoRR abs/1402.3609 (2014) - [i27]Clément L. Canonne, Ronitt Rubinfeld:
Testing probability distributions underlying aggregated data. CoRR abs/1402.3835 (2014) - [i26]Albert Kim, Eric Blais, Aditya G. Parameswaran, Piotr Indyk, Sam Madden, Ronitt Rubinfeld:
Rapid Sampling for Visualizations with Ordering Guarantees. CoRR abs/1412.3040 (2014) - [i25]Sheela Devadas, Ronitt Rubinfeld:
A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness. CoRR abs/1412.5484 (2014) - [i24]Clément L. Canonne, Ronitt Rubinfeld:
Testing probability distributions underlying aggregated data. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j38]Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith:
Sublinear Algorithms for Approximating String Compressibility. Algorithmica 65(3): 685-709 (2013) - [j37]Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White:
Testing Closeness of Discrete Distributions. J. ACM 60(1): 4:1-4:25 (2013) - [j36]Ronitt Rubinfeld, Ning Xie:
Robust characterizations of k-wise independence over product spaces and related testing results. Random Struct. Algorithms 43(3): 265-312 (2013) - [j35]Reut Levi, Dana Ron, Ronitt Rubinfeld:
Testing Properties of Collections of Distributions. Theory Comput. 9: 295-347 (2013) - [c57]Andrea Campagna, Alan Guo, Ronitt Rubinfeld:
Local Reconstructors and Tolerant Testers for Connectivity and Diameter. APPROX-RANDOM 2013: 411-424 - [c56]Akashnil Dutta, Reut Levi, Dana Ron, Ronitt Rubinfeld:
A Simple Online Competitive Adaptation of Lempel-Ziv Compression with Efficient Random Access Support. DCC 2013: 113-122 - [i23]Akashnil Dutta, Reut Levi, Dana Ron, Ronitt Rubinfeld:
A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support. CoRR abs/1301.2495 (2013) - 2012
- [j34]Ronitt Rubinfeld:
Taming big probability distributions. XRDS 19(1): 24-28 (2012) - [j33]Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, Omri Weinstein:
Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity. ACM Trans. Comput. Theory 4(4): 11:1-11:12 (2012) - [c55]Reut Levi, Dana Ron, Ronitt Rubinfeld:
Testing Similar Means. ICALP (1) 2012: 629-640 - [c54]Piotr Indyk, Reut Levi, Ronitt Rubinfeld:
Approximating and testing k-histogram distributions in sub-linear time. PODS 2012: 15-22 - [c53]Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld:
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. SODA 2012: 1123-1131 - [c52]Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie:
Space-efficient local computation algorithms. SODA 2012: 1132-1139 - [i22]Andrea Campagna, Alan Guo, Ronitt Rubinfeld:
Local reconstructors and tolerant testers for connectivity and diameter. CoRR abs/1208.2956 (2012) - [i21]Reut Levi, Dana Ron, Ronitt Rubinfeld:
Testing Similar Means. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j32]Khanh Do Ba, Huy L. Nguyen, Huy N. Nguyen, Ronitt Rubinfeld:
Sublinear Time Algorithms for Earth Mover's Distance. Theory Comput. Syst. 48(2): 428-442 (2011) - [j31]Ronitt Rubinfeld, Asaf Shapira:
Sublinear Time Algorithms. SIAM J. Discret. Math. 25(4): 1562-1588 (2011) - [c51]Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein:
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity. APPROX-RANDOM 2011: 664-675 - [c50]Reut Levi, Dana Ron, Ronitt Rubinfeld:
Testing Properties of Collections of Distributions. ICS 2011: 179-194 - [c49]Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie:
Fast Local Computation Algorithms. ICS 2011: 223-238 - [c48]Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant:
Testing monotonicity of distributions over general partial orders. ICS 2011: 239-252 - [i20]Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein:
Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity. CoRR abs/1101.5345 (2011) - [i19]Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie:
Fast Local Computation Algorithms. CoRR abs/1104.1377 (2011) - [i18]Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie:
Space-efficient Local Computation Algorithms. CoRR abs/1109.6178 (2011) - [i17]Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld:
A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size. CoRR abs/1110.1079 (2011) - [i16]Piotr Indyk, Reut Levi, Ronitt Rubinfeld:
Approximating and Testing k-Histogram Distributions in Sub-linear time. Electron. Colloquium Comput. Complex. TR11 (2011) - [i15]Ronitt Rubinfeld, Asaf Shapira:
Sublinear Time Algorithms. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j30]Elena Grigorescu, Kyomin Jung, Ronitt Rubinfeld:
A local decision test for sparse polynomials. Inf. Process. Lett. 110(20): 898-901 (2010) - [j29]Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing Halfspaces. SIAM J. Comput. 39(5): 2004-2047 (2010) - [c47]Ronitt Rubinfeld, Ning Xie:
Testing Non-uniform k-Wise Independent Distributions over Product Spaces. ICALP (1) 2010: 565-581 - [c46]Krzysztof Onak, Ronitt Rubinfeld:
Maintaining a large matching and a small vertex cover. STOC 2010: 457-464 - [c45]Rubi Boim, Haim Kaplan, Tova Milo, Ronitt Rubinfeld:
Improved Recommendations via (More) Collaboration. WebDB 2010 - [p3]Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld:
Sublinear Algorithms in the External Memory Model. Property Testing 2010: 240-243 - [p2]Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing (Subclasses of) Halfspaces. Property Testing 2010: 334-340 - [p1]Krzysztof Onak, Ronitt Rubinfeld:
Dynamic Approximate Vertex Cover and Maximum Matching. Property Testing 2010: 341-345 - [i14]Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White:
Testing Closeness of Discrete Distributions. CoRR abs/1009.5397 (2010) - [i13]Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant:
Testing monotonicity of distributions over general partial orders. Electron. Colloquium Comput. Complex. TR10 (2010) - [i12]Reut Levi, Dana Ron, Ronitt Rubinfeld:
Testing Properties of Collections of Distributions. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j28]Ronitt Rubinfeld, Rocco A. Servedio:
Testing monotone high-dimensional distributions. Random Struct. Algorithms 34(1): 24-44 (2009) - [c44]Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing ±1-weight halfspace. APPROX-RANDOM 2009: 646-657 - [c43]Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld:
External Sampling. ICALP (1) 2009: 83-94 - [c42]Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing halfspaces. SODA 2009: 256-264 - [i11]Khanh Do Ba, Huy L. Nguyen, Huy N. Nguyen, Ronitt Rubinfeld:
Sublinear Time Algorithms for Earth Mover's Distance. CoRR abs/0904.0292 (2009) - 2008
- [j27]Michael Ben-Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld:
Non-abelian homomorphism testing, and distributions close to their self-convolutions. Random Struct. Algorithms 32(1): 49-70 (2008) - [e3]Ashish Goel, Klaus Jansen, José D. P. Rolim, Ronitt Rubinfeld:
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008. Proceedings. Lecture Notes in Computer Science 5171, Springer 2008, ISBN 978-3-540-85362-6 [contents] - [e2]Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler:
Sublinear Algorithms, 17.08. - 22.08.2008. Dagstuhl Seminar Proceedings 08341, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany 2008 [contents] - [r1]Ronitt Rubinfeld:
Linearity Testing/Testing Hadamard Codes. Encyclopedia of Algorithms 2008 - [i10]Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler:
08341 Abstracts Collection - Sublinear Algorithms. Sublinear Algorithms 2008 - [i9]Artur Czumaj, S. Muthukrishnan, Ronitt Rubinfeld, Christian Sohler:
08341 Executive Summary - Sublinear Algorithms. Sublinear Algorithms 2008 - 2007
- [c41]Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith:
Sublinear Algorithms for Approximating String Compressibility. APPROX-RANDOM 2007: 609-623 - [c40]Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan:
Testing for Concise Representations. FOCS 2007: 549-558 - [c39]Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie:
Testing k-wise and almost k-wise independence. STOC 2007: 496-505 - [i8]Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith:
Sublinear Algorithms for Approximating String Compressibility. CoRR abs/0706.1084 (2007) - [i7]Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan:
Testing for Concise Representations. Electron. Colloquium Comput. Complex. TR07 (2007) - [i6]Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing Halfspaces. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j26]Michal Parnas, Dana Ron, Ronitt Rubinfeld:
Tolerant property testing and distance approximation. J. Comput. Syst. Sci. 72(6): 1012-1042 (2006) - [e1]Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler:
Sublinear Algorithms, 17.07. - 22.07.2005. Dagstuhl Seminar Proceedings 05291, Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany 2006 [contents] - 2005
- [j25]Tugkan Batu, Ronitt Rubinfeld, Patrick White:
Fast approximate PCPs for multidimensional bin-packing problems. Inf. Comput. 196(1): 42-56 (2005) - [j24]Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan:
Approximating the Minimum Spanning Tree Weight in Sublinear Time. SIAM J. Comput. 34(6): 1370-1379 (2005) - [j23]Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler:
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time. SIAM J. Comput. 35(1): 91-109 (2005) - [j22]Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld:
The Complexity of Approximating the Entropy. SIAM J. Comput. 35(1): 132-150 (2005) - [c38]Ronitt Rubinfeld, Rocco A. Servedio:
Testing monotone high-dimensional distributions. STOC 2005: 147-156 - [i5]Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler:
05291 Abstracts Collection -- Sublinear Algorithms. Sublinear Algorithms 2005 - [i4]Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam D. Smith:
Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j21]Funda Ergün, Ravi Kumar, Ronitt Rubinfeld:
Fast approximate probabilistically checkable proofs. Inf. Comput. 189(2): 135-159 (2004) - [c37]Michael Ben-Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld:
Non-Abelian Homomorphism Testing, and Distributions Close to Their Self-convolutions. APPROX-RANDOM 2004: 273-285 - [c36]Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, Ayellet Tal:
The Bloomier filter: an efficient data structure for static support lookup tables. SODA 2004: 30-39 - [c35]Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld:
Sublinear algorithms for testing monotone and unimodal distributions. STOC 2004: 381-390 - [i3]Michal Parnas, Dana Ron, Ronitt Rubinfeld:
Tolerant Property Testing and Distance Approximation. Electron. Colloquium Comput. Complex. TR04 (2004) - [i2]Michael Ben-Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld:
Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j20]Michal Parnas, Dana Ron, Ronitt Rubinfeld:
Testing membership in parenthesis languages. Random Struct. Algorithms 22(1): 98-138 (2003) - [j19]Michal Parnas, Dana Ron, Ronitt Rubinfeld:
On Testing Convexity and Submodularity. SIAM J. Comput. 32(5): 1158-1184 (2003) - [j18]Ravi Kumar, Ronitt Rubinfeld:
Algorithms column: sublinear time algorithms. SIGACT News 34(4): 57-67 (2003) - [c34]Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler:
Sublinear-time approximation of Euclidean minimum spanning tree. SODA 2003: 813-822 - [c33]Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami:
A sublinear algorithm for weakly approximating edit distance. STOC 2003: 316-324 - 2002
- [c32]Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld:
The Complexity of Approximating the Entropy. CCC 2002: 17 - [c31]Michal Parnas, Dana Ron, Ronitt Rubinfeld:
On Testing Convexity and Submodularity. RANDOM 2002: 11-25 - [c30]Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky:
Monotonicity testing over general poset domains. STOC 2002: 474-483 - [c29]Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld:
The complexity of approximating entropy. STOC 2002: 678-687 - 2001
- [j17]Funda Ergün, Ravi Kumar, Ronitt Rubinfeld:
Checking Approximate Computations of Polynomials and Functional Equations. SIAM J. Comput. 31(2): 550-576 (2001) - [c28]Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, Patrick White:
Testing Random Variables for Independence and Identity. FOCS 2001: 442-451 - [c27]Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan:
Approximating the Minimum Spanning Tree Weight in Sublinear Time. ICALP 2001: 190-200 - [c26]Ran Canetti, Yuval Ishai, Ravi Kumar, Michael K. Reiter, Ronitt Rubinfeld, Rebecca N. Wright:
Selective private function evaluation with applications to private statistics. PODC 2001: 293-304 - [c25]Michal Parnas, Dana Ron, Ronitt Rubinfeld:
Testing Parenthesis Languages. RANDOM-APPROX 2001: 261-272 - 2000
- [j16]Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan:
Spot-Checkers. J. Comput. Syst. Sci. 60(3): 717-751 (2000) - [j15]Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan:
Learning Polynomials with Queries: The Highly Noisy Case. SIAM J. Discret. Math. 13(4): 535-570 (2000) - [c24]Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White:
Testing that distributions are close. FOCS 2000: 259-269 - [c23]Ronald Fagin, Anna R. Karlin, Jon M. Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, Andrew Tomkins:
Random walks with "back buttons" (extended abstract). STOC 2000: 484-493
1990 – 1999
- 1999
- [j14]Ronitt Rubinfeld:
On the Robustness of Functional Equations. SIAM J. Comput. 28(6): 1972-1997 (1999) - [c22]Tugkan Batu, Ronitt Rubinfeld, Patrick White:
Fast Approximate PCPs for Multidimensional Bin-Packing Problems. RANDOM-APPROX 1999: 245-256 - [c21]Funda Ergün, Ravi Kumar, Ronitt Rubinfeld:
Fast Approximate PCPs. STOC 1999: 41-50 - 1998
- [j13]Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan:
Reconstructing Algebraic Functions from Mixed Data. SIAM J. Comput. 28(2): 487-510 (1998) - [c20]Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan:
Spot-Checkers. STOC 1998: 259-268 - [i1]Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan:
Learning Polynomials with Queries - The Highly Noisy Case. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [j12]Yoav Freund, Michael J. Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie:
Efficient Learning of Typical Finite Automata from Random Walks. Inf. Comput. 138(1): 23-48 (1997) - [j11]Dana Ron, Ronitt Rubinfeld:
Exactly Learning Automata of Small Cover Time. Mach. Learn. 27(1): 69-96 (1997) - [c19]Funda Ergün, Ravi Kumar, Ronitt Rubinfeld:
Learning Distributions from Random Walks. COLT 1997: 243-249 - 1996
- [j10]Ronitt Rubinfeld:
Designing Checkers for Programs that Run in Parallel. Algorithmica 15(4): 287-301 (1996) - [j9]Ronitt Rubinfeld, Madhu Sudan:
Robust Characterizations of Polynomials with Applications to Program Testing. SIAM J. Comput. 25(2): 252-271 (1996) - [c18]Jon M. Kleinberg, Ronitt Rubinfeld:
Short Paths in Expander Graphs. FOCS 1996: 86-95 - [c17]Funda Ergün, Ravi Kumar, Ronitt Rubinfeld:
Approximate Checking of Polynomials and Functional Equations (extended abstract). FOCS 1996: 592-601 - 1995
- [j8]Dana Ron, Ronitt Rubinfeld:
Learning Fallible Deterministic Finite Automata. Mach. Learn. 18(2-3): 149-185 (1995) - [c16]Funda Ergün, Ravi Kumar, Ronitt Rubinfeld:
On Learning Bounded-Width Branching Programs. COLT 1995: 361-368 - [c15]Dana Ron, Ronitt Rubinfeld:
Exactly Learning Automata with Small Cover Time. COLT 1995: 427-436 - [c14]Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan:
Learning Polynomials with Queries: The Highly Noisy Case. FOCS 1995: 294-303 - [c13]Yoav Freund, Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire:
Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries. FOCS 1995: 332-341 - 1994
- [c12]Ronitt Rubinfeld, Richard Zippel:
A new modular interpolation algorithm for factoring multivariate polynominals. ANTS 1994: 93-107 - [c11]Ronitt Rubinfeld:
On the robustness of functional equations. FOCS 1994: 288-299 - [c10]Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie:
On the learnability of discrete distributions. STOC 1994: 273-282 - 1993
- [j7]Manuel Blum, Michael Luby, Ronitt Rubinfeld:
Self-Testing/Correcting with Applications to Numerical Problems. J. Comput. Syst. Sci. 47(3): 549-595 (1993) - [c9]Dana Ron, Ronitt Rubinfeld:
Learning Fallible Finite State Automata. COLT 1993: 218-227 - [c8]Yoav Freund, Michael J. Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie:
Efficient learning of typical finite automata from random walks. STOC 1993: 315-324 - 1992
- [j6]Ronitt Rubinfeld:
Batch Checking with Applications to Linear Functions. Inf. Process. Lett. 42(2): 77-80 (1992) - [j5]Sandy Irani, Moni Naor, Ronitt Rubinfeld:
On the Time and Space Complexity of Computation Using Write-Once Memory Or Is Pen Really Much Worse Than Pencil? Math. Syst. Theory 25(2): 141-159 (1992) - [c7]Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan:
Reconstructing Algebraic Functions from Mixed Data. FOCS 1992: 503-512 - [c6]Ronitt Rubinfeld, Madhu Sudan:
Self-Testing Polynomial Functions Efficiently and Over Rational Domains. SODA 1992: 23-32 - 1991
- [j4]Sandy Irani, Ronitt Rubinfeld:
A Competitive 2-Server Algorithm. Inf. Process. Lett. 39(2): 85-91 (1991) - [c5]Joe Kilian, Ronitt Rubinfeld:
Interactive Proofs with Space Bounded Provers. CRYPTO 1991: 225-231 - [c4]Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson:
Self-Testing/Correcting for Polynomials and for Approximate Functions. STOC 1991: 32-42 - 1990
- [j3]Ronitt Rubinfeld:
The Cover Time of a Regular Expander is O(n log n). Inf. Process. Lett. 35(1): 49-51 (1990) - [c3]Manuel Blum, Michael Luby, Ronitt Rubinfeld:
Self-Testing/Correcting with Applications to Numerical Problems. STOC 1990: 73-83
1980 – 1989
- 1989
- [j2]Nancy M. Amato, Manuel Blum, Sandy Irani, Ronitt Rubinfeld:
Reversing Trains: A Turn of the Century Sorting Problem. J. Algorithms 10(3): 413-428 (1989) - [c2]Manuel Blum, Michael Luby, Ronitt Rubinfeld:
Program Result Checking against Adaptive Programs and in Cryptographic Settings. Distributed Computing And Cryptography 1989: 107-118 - 1987
- [j1]James Barber, Richard A. Volz, Rajiv S. Desai, Ronitt Rubinfeld, Brian Schipper, Jan D. Wolter:
Automatic evaluation of two-fingered grips. IEEE J. Robotics Autom. 3(4): 356-361 (1987) - 1986
- [c1]James Barber, Richard A. Volz, Rajiv S. Desai, Ronitt Rubinfeld, Brian Schipper, Jan D. Wolter:
Automatic two-fingered grip selection. ICRA 1986: 890-896
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-01-21 00:03 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
