Ronitt Rubinfeld

230 papers A* 61A 15B 4Misc 1Journal 116Unranked 24
YearRankTypeTitle / Venue / Authors
2026 J jnl
Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates.
CoRR
Slobodan Mitrovic, Srikkanth Ramachandran, Ronitt Rubinfeld, Mihir Singhal
2026 A conf
Testable Algorithms for Approximately Counting Edges and Triangles in Sublinear Time and Space.
ITCS
Talya Eden, Ronitt Rubinfeld, Arsen Vasilyan
2025 A conf
A Fast Coloring Oracle for Average Case Hypergraphs.
APPROX/RANDOM
Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber
2025 J jnl
A Fast Coloring Oracle for Average Case Hypergraphs.
CoRR
Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber
2025 A* conf
Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time.
STOC
Talya Eden, Reut Levi, Dana Ron, Ronitt Rubinfeld
2025 J jnl
Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time.
CoRR
Talya Eden, Reut Levi, Dana Ron, Ronitt Rubinfeld
2025 A* conf
Better Private Distribution Testing by Leveraging Unverified Auxiliary Data.
COLT
Maryam Aliakbarpour, Arnav Burudgunte, Clément L. Canonne, Ronitt Rubinfeld
2025 J jnl
Better Private Distribution Testing by Leveraging Unverified Auxiliary Data.
CoRR
Maryam Aliakbarpour, Arnav Burudgunte, Clément Cannone, Ronitt Rubinfeld
2025 J jnl
Locally computing edge orientations.
CoRR
Slobodan Mitrovic, Ronitt Rubinfeld, Mihir Singhal
2025 J jnl
No Price Tags? No Problem: Query Strategies for Unpriced Information.
CoRR
Shivam Nadimpalli, Mingda Qiao, Ronitt Rubinfeld
2025 B conf
Optimal and learned algorithms for the online list update problem with Zipfian accesses.
ALT
Piotr Indyk, Isabelle Quaye, Ronitt Rubinfeld, Sandeep Silwal
2025 J jnl
Quality control in sublinear time: a case study via random graphs.
CoRR
Cassandra Marcussen, Ronitt Rubinfeld, Madhu Sudan
2025 A* conf
Stochastic Matching via In-n-Out Local Computation Algorithms.
STOC
Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Ronitt Rubinfeld
2025 J jnl
Testable algorithms for approximately counting edges and triangles in sublinear time and space.
CoRR
Talya Eden, Ronitt Rubinfeld, Arsen Vasilyan
2024 J jnl
Average-Case Local Computation Algorithms.
CoRR
Amartya Shankha Biswas, Ruidi Cao, Edward Pyne, Ronitt Rubinfeld
2024 A conf
Locally Computing Edge Orientations.
ESA
Slobodan Mitrovic, Ronitt Rubinfeld, Mihir Singhal
2024 J jnl
New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling.
Algorithmica
Spencer Compton, Slobodan Mitrovic, Ronitt Rubinfeld
2024 A* conf
Optimal Algorithms for Augmented Testing of Discrete Distributions.
NeurIPS
Maryam Aliakbarpour, Piotr Indyk, Ronitt Rubinfeld, Sandeep Silwal
2024 J jnl
Optimal Algorithms for Augmented Testing of Discrete Distributions.
CoRR
Maryam Aliakbarpour, Piotr Indyk, Ronitt Rubinfeld, Sandeep Silwal
2024 J jnl
Stochastic Matching via In-n-Out Local Computation Algorithms.
CoRR
Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Ronitt Rubinfeld
2023 J jnl
From Big Data Theory to Big Data Practice (Dagstuhl Seminar 23071).
Dagstuhl Reports
Martin Farach-Colton, Fabian Daniel Kuhn, Ronitt Rubinfeld, Przemyslaw Uznanski
2023 A* conf
New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling.
ICALP
Spencer Compton, Slobodan Mitrovic, Ronitt Rubinfeld
2023 A* conf
Testing Distributional Assumptions of Learning Algorithms.
STOC
Ronitt Rubinfeld, Arsen Vasilyan
2023 B conf
Testing Tail Weight of a Distribution Via Hazard Rate.
ALT
Maryam Aliakbarpour, Amartya Shankha Biswas, Kavya Ravichandran, Ronitt Rubinfeld
2022 A* conf
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks.
NeurIPS
Anders Aamand, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer, Sandeep Silwal, Tal Wagner
2022 J jnl
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks.
CoRR
Anders Aamand, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer, Sandeep Silwal, Tal Wagner
2022 A conf
Local Access to Random Walks.
ITCS
Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld
2022 A conf
Massively Parallel Algorithms for Small Subgraph Counting.
APPROX/RANDOM
Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Ronitt Rubinfeld, Slobodan Mitrovic
2022 A conf
Online Page Migration with ML Advice.
AISTATS
Piotr Indyk, Frederik Mallmann-Trenn, Slobodan Mitrovic, Ronitt Rubinfeld
2022 A* conf
Properly learning monotone functions via local correction.
FOCS
Jane Lange, Ronitt Rubinfeld, Arsen Vasilyan
2022 J jnl
Properly learning monotone functions via local reconstruction.
CoRR
Jane Lange, Ronitt Rubinfeld, Arsen Vasilyan
2022 J jnl
Testing distributional assumptions of learning algorithms.
CoRR
Ronitt Rubinfeld, Arsen Vasilyan
2022 A* conf
Triangle and Four Cycle Counting with Predictions in Graph Streams.
ICLR
Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang
2022 J jnl
Triangle and Four Cycle Counting with Predictions in Graph Streams.
CoRR
Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang
2021 A* conf
Learning-based Support Estimation in Sublinear Time.
ICLR
Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner
2021 J jnl
Learning-based Support Estimation in Sublinear Time.
CoRR
Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner
2021 J jnl
Local Access to Random Walks.
CoRR
Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld
2021 A* conf
Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees.
ICDE
Stephen Macke, Maryam Aliakbarpour, Ilias Diakonikolas, Aditya G. Parameswaran, Ronitt Rubinfeld
2021 — conf
Sampling Multiple Edges Efficiently.
APPROX-RANDOM
Talya Eden, Saleet Mossel, Ronitt Rubinfeld
2021 — conf
Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time.
APPROX-RANDOM
Amartya Shankha Biswas, Talya Eden, Ronitt Rubinfeld
2021 J jnl
Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time.
CoRR
Amartya Shankha Biswas, Talya Eden, Ronitt Rubinfeld
2020 J jnl
Amortized Edge Sampling.
CoRR
Talya Eden, Saleet Mossel, Ronitt Rubinfeld
2020 A* conf
Improved Local Computation Algorithm for Set Cover via Sparsification.
SODA
Christoph Grunau, Slobodan Mitrovic, Ronitt Rubinfeld, Ali Vakilian
2020 A conf
Local Access to Huge Random Objects Through Partial Sampling.
ITCS
Amartya Shankha Biswas, Ronitt Rubinfeld, Anak Yodpinyanee
2020 J jnl
Local Algorithms for Sparse Spanning Graphs.
Algorithmica
Reut Levi, Dana Ron, Ronitt Rubinfeld
2020 A conf
Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples.
ITCS
Ronitt Rubinfeld, Arsen Vasilyan
2020 J jnl
Monotone probability distributions over the Boolean cube can be learned with sublinear samples.
CoRR
Ronitt Rubinfeld, Arsen Vasilyan
2020 J jnl
New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling.
CoRR
Spencer Compton, Slobodan Mitrovic, Ronitt Rubinfeld
2020 J jnl
Online Page Migration with ML Advice.
CoRR
Piotr Indyk, Frederik Mallmann-Trenn, Slobodan Mitrovic, Ronitt Rubinfeld
2020 J jnl
Parallel Algorithms for Small Subgraph Counting.
CoRR
Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Slobodan Mitrovic, Ronitt Rubinfeld
2020 J jnl
Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees.
CoRR
Stephen Macke, Maryam Aliakbarpour, Ilias Diakonikolas, Aditya G. Parameswaran, Ronitt Rubinfeld
2020 J jnl
Testing Tail Weight of a Distribution Via Hazard Rate.
CoRR
Maryam Aliakbarpour, Amartya Shankha Biswas, Kavya Ravichandran, Ronitt Rubinfeld
2019 — conf
Approximating the Noise Sensitivity of a Monotone Boolean Function.
APPROX-RANDOM
Ronitt Rubinfeld, Arsen Vasilyan
2019 J jnl
Approximating the noise sensitivity of a monotone Boolean function.
CoRR
Ronitt Rubinfeld, Arsen Vasilyan
2019 J jnl
Improved Local Computation Algorithm for Set Cover via Sparsification.
CoRR
Christoph Grunau, Slobodan Mitrovic, Ronitt Rubinfeld, Ali Vakilian
2019 A conf
Local Computation Algorithms for Spanners.
ITCS
Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee
2019 J jnl
Local Computation Algorithms for Spanners.
CoRR
Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee
2019 A* conf
Local Computation Algorithms.
PODC
Ronitt Rubinfeld
2019 A* conf
Private Testing of Distributions via Sample Permutations.
NeurIPS
Maryam Aliakbarpour, Ilias Diakonikolas, Daniel Kane, Ronitt Rubinfeld
2019 J jnl
Set Cover in Sub-linear Time.
CoRR
Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee
2019 A* conf
Testing Mixtures of Discrete Distributions.
COLT
Maryam Aliakbarpour, Ravi Kumar, Ronitt Rubinfeld
2019 J jnl
Testing Mixtures of Discrete Distributions.
CoRR
Maryam Aliakbarpour, Ravi Kumar, Ronitt Rubinfeld
2019 A* conf
Towards Testing Monotonicity of Distributions Over General Posets.
COLT
Maryam Aliakbarpour, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee
2019 J jnl
Towards Testing Monotonicity of Distributions Over General Posets.
CoRR
Maryam Aliakbarpour, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee
2018 A* conf
Differentially Private Identity and Equivalence Testing of Discrete Distributions.
ICML
Maryam Aliakbarpour, Ilias Diakonikolas, Ronitt Rubinfeld
2018 A* conf
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover.
PODC
Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, Ronitt Rubinfeld
2018 J jnl
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover.
CoRR
Mohsen Ghaffari, Themis Gouleakis, Slobodan Mitrovic, Ronitt Rubinfeld
2018 J jnl
Sampling Correctors.
SIAM J. Comput.
Clément L. Canonne, Themis Gouleakis, Ronitt Rubinfeld
2018 A* conf
Set Cover in Sub-linear Time.
SODA
Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee
2018 J jnl
Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling.
Algorithmica
Maryam Aliakbarpour, Amartya Shankha Biswas, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee
2018 J jnl
Testing Shape Restrictions of Discrete Distributions.
Theory Comput. Syst.
Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, Ronitt Rubinfeld
2017 Misc conf
Can We Locally Compute Sparse Connected Subgraphs?
CSR
Ronitt Rubinfeld
2017 J jnl
Constructing near spanning trees with few local inspections.
Random Struct. Algorithms
Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira
2017 J jnl
Differentially Private Identity and Closeness Testing of Discrete Distributions.
CoRR
Maryam Aliakbarpour, Ilias Diakonikolas, Ronitt Rubinfeld
2017 — conf
Fractional Set Cover in the Streaming Model.
APPROX-RANDOM
Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan R. Ullman, Ali Vakilian, Anak Yodpinyanee
2017 J jnl
I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making.
Proc. VLDB Endow.
Sajjadur Rahman, Maryam Aliakbarpour, Hidy Kong, Eric Blais, Karrie Karahalios, Aditya G. Parameswaran, Ronitt Rubinfeld
2017 A* conf
Local Computation Algorithms (Invited Talk).
ICALP
Ronitt Rubinfeld
2017 J jnl
Local Computation Algorithms for Graphs of Non-constant Degrees.
Algorithmica
Reut Levi, Ronitt Rubinfeld, Anak Yodpinyanee
2017 J jnl
Local-Access Generators for Basic Random Graph Models.
CoRR
Amartya Shankha Biswas, Ronitt Rubinfeld, Anak Yodpinyanee
2016 — conf
A Local Algorithm for Constructing Spanners in Minor-Free Graphs.
APPROX-RANDOM
Reut Levi, Dana Ron, Ronitt Rubinfeld
2016 J jnl
A Local Algorithm for Constructing Spanners in Minor-Free Graphs.
CoRR
Reut Levi, Dana Ron, Ronitt Rubinfeld
2016 J jnl
A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness.
Theory Comput. Syst.
Sheela Devadas, Ronitt Rubinfeld
2016 A* conf
Learning and Testing Junta Distributions.
COLT
Maryam Aliakbarpour, Eric Blais, Ronitt Rubinfeld
2016 — ch.
Linearity Testing/Testing Hadamard Codes.
Encyclopedia of Algorithms
Sofya Raskhodnikova, Ronitt Rubinfeld
2016 A conf
Sampling Correctors.
ITCS
Clément L. Canonne, Themis Gouleakis, Ronitt Rubinfeld
2016 — ch.
Something for (Almost) Nothing: New Advances in Sublinear-Time Algorithms.
Handbook of Big Data
Ronitt Rubinfeld, Eric Blais
2016 J jnl
Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation.
CoRR
Maryam Aliakbarpour, Amartya Shankha Biswas, Themistoklis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee
2016 A conf
Testing Shape Restrictions of Discrete Distributions.
STACS
Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, Ronitt Rubinfeld
2015 B conf
Brief Announcement: Local Computation Algorithms for Graphs of Non-Constant Degrees.
SPAA
Reut Levi, Ronitt Rubinfeld, Anak Yodpinyanee
2015 J jnl
Constructing Near Spanning Trees with Few Local Inspections.
CoRR
Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira
2015 J jnl
Constructing Near Spanning Trees with Few Local Inspections.
Electron. Colloquium Comput. Complex.
Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira
2015 A* conf
Erratum for: Approximating and Testing
PODS
Piotr Indyk, Reut Levi, Ronitt Rubinfeld
2015 J jnl
Local Computation Algorithms for Graphs of Non-Constant Degrees.
CoRR
Reut Levi, Ronitt Rubinfeld, Anak Yodpinyanee
2015 A* ed.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015
STOC
Rocco A. Servedio, Ronitt Rubinfeld
2015 J jnl
Rapid Sampling for Visualizations with Ordering Guarantees.
Proc. VLDB Endow.
Albert Kim, Eric Blais, Aditya G. Parameswaran, Piotr Indyk, Samuel Madden, Ronitt Rubinfeld
2015 J jnl
Sampling Correctors.
CoRR
Clément L. Canonne, Themis Gouleakis, Ronitt Rubinfeld
2015 J jnl
Testing Shape Restrictions of Discrete Distributions.
CoRR
Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, Ronitt Rubinfeld
2014 J jnl
A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness.
CoRR
Sheela Devadas, Ronitt Rubinfeld
2014 — conf
Local Algorithms for Sparse Spanning Graphs.
APPROX-RANDOM
Reut Levi, Dana Ron, Ronitt Rubinfeld
2014 J jnl
Local Algorithms for Sparse Spanning Graphs.
CoRR
Reut Levi, Dana Ron, Ronitt Rubinfeld
2014 J jnl
Rapid Sampling for Visualizations with Ordering Guarantees.
CoRR
Albert Kim, Eric Blais, Aditya G. Parameswaran, Piotr Indyk, Sam Madden, Ronitt Rubinfeld
2014 — conf
Testing Probability Distributions Underlying Aggregated Data.
ICALP (1)
Clément L. Canonne, Ronitt Rubinfeld
2014 J jnl
Testing Similar Means.
SIAM J. Discret. Math.
Reut Levi, Dana Ron, Ronitt Rubinfeld
2014 J jnl
Testing probability distributions underlying aggregated data.
CoRR
Clément L. Canonne, Ronitt Rubinfeld
2014 J jnl
Testing probability distributions underlying aggregated data.
Electron. Colloquium Comput. Complex.
Clément L. Canonne, Ronitt Rubinfeld
2013 B conf
A Simple Online Competitive Adaptation of Lempel-Ziv Compression with Efficient Random Access Support.
DCC
Akashnil Dutta, Reut Levi, Dana Ron, Ronitt Rubinfeld
2013 J jnl
A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support
CoRR
Akashnil Dutta, Reut Levi, Dana Ron, Ronitt Rubinfeld
2013 — conf
Local Reconstructors and Tolerant Testers for Connectivity and Diameter.
APPROX-RANDOM
Andrea Campagna, Alan Guo, Ronitt Rubinfeld
2013 J jnl
Robust characterizations of
Random Struct. Algorithms
Ronitt Rubinfeld, Ning Xie
2013 J jnl
Sublinear Algorithms for Approximating String Compressibility.
Algorithmica
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith
2013 J jnl
Testing Closeness of Discrete Distributions.
J. ACM
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
2013 J jnl
Testing Properties of Collections of Distributions.
Theory Comput.
Reut Levi, Dana Ron, Ronitt Rubinfeld
2012 A* conf
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size.
SODA
Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld
2012 A* conf
Approximating and testing k-histogram distributions in sub-linear time.
PODS
Piotr Indyk, Reut Levi, Ronitt Rubinfeld
2012 J jnl
Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity.
ACM Trans. Comput. Theory
Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, Omri Weinstein
2012 J jnl
Local reconstructors and tolerant testers for connectivity and diameter
CoRR
Andrea Campagna, Alan Guo, Ronitt Rubinfeld
2012 A* conf
Space-efficient local computation algorithms.
SODA
Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie
2012 J jnl
Taming big probability distributions.
XRDS
Ronitt Rubinfeld
2012 — conf
Testing Similar Means.
ICALP (1)
Reut Levi, Dana Ron, Ronitt Rubinfeld
2012 J jnl
Testing Similar Means.
Electron. Colloquium Comput. Complex.
Reut Levi, Dana Ron, Ronitt Rubinfeld
2011 J jnl
A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size
CoRR
Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld
2011 J jnl
Approximating and Testing
Electron. Colloquium Comput. Complex.
Piotr Indyk, Reut Levi, Ronitt Rubinfeld
2011 — conf
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity.
APPROX-RANDOM
Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein
2011 J jnl
Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity
CoRR
Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein
2011 J jnl
Fast Local Computation Algorithms
CoRR
Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie
2011 A conf
Fast Local Computation Algorithms.
ICS
Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie
2011 J jnl
Space-efficient Local Computation Algorithms
CoRR
Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie
2011 J jnl
Sublinear Time Algorithms for Earth Mover's Distance.
Theory Comput. Syst.
Khanh Do Ba, Huy L. Nguyen, Huy N. Nguyen, Ronitt Rubinfeld
2011 J jnl
Sublinear Time Algorithms.
Electron. Colloquium Comput. Complex.
Ronitt Rubinfeld, Asaf Shapira
2011 J jnl
Sublinear Time Algorithms.
SIAM J. Discret. Math.
Ronitt Rubinfeld, Asaf Shapira
2011 A conf
Testing Properties of Collections of Distributions.
ICS
Reut Levi, Dana Ron, Ronitt Rubinfeld
2011 A conf
Testing monotonicity of distributions over general partial orders.
ICS
Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant
2010 J jnl
A local decision test for sparse polynomials.
Inf. Process. Lett.
Elena Grigorescu, Kyomin Jung, Ronitt Rubinfeld
2010 — ch.
Dynamic Approximate Vertex Cover and Maximum Matching.
Property Testing
Krzysztof Onak, Ronitt Rubinfeld
2010 — conf
Improved Recommendations via (More) Collaboration.
WebDB
Rubi Boim, Haim Kaplan, Tova Milo, Ronitt Rubinfeld
2010 A* conf
Maintaining a large matching and a small vertex cover.
STOC
Krzysztof Onak, Ronitt Rubinfeld
2010 — ch.
Sublinear Algorithms in the External Memory Model.
Property Testing
Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld
2010 — ch.
Testing (Subclasses of) Halfspaces.
Property Testing
Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio
2010 J jnl
Testing Closeness of Discrete Distributions
CoRR
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
2010 J jnl
Testing Halfspaces.
SIAM J. Comput.
Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio
2010 — conf
Testing Non-uniform
ICALP (1)
Ronitt Rubinfeld, Ning Xie
2010 J jnl
Testing Properties of Collections of Distributions.
Electron. Colloquium Comput. Complex.
Reut Levi, Dana Ron, Ronitt Rubinfeld
2010 J jnl
Testing monotonicity of distributions over general partial orders.
Electron. Colloquium Comput. Complex.
Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant
2009 — conf
External Sampling.
ICALP (1)
Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld
2009 J jnl
Sublinear Time Algorithms for Earth Mover's Distance
CoRR
Khanh Do Ba, Huy L. Nguyen, Huy N. Nguyen, Ronitt Rubinfeld
2009 A* conf
Testing halfspaces.
SODA
Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio
2009 J jnl
Testing monotone high-dimensional distributions.
Random Struct. Algorithms
Ronitt Rubinfeld, Rocco A. Servedio
2009 — conf
Testing ±1-weight halfspace.
APPROX-RANDOM
Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio
2008 — conf
08341 Abstracts Collection - Sublinear Algorithms.
Sublinear Algorithms
Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler
2008 — conf
08341 Executive Summary - Sublinear Algorithms.
Sublinear Algorithms
Artur Czumaj, S. Muthukrishnan, Ronitt Rubinfeld, Christian Sohler
2008 — ed.
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
APPROX-RANDOM
Ashish Goel, Klaus Jansen, José D. P. Rolim, Ronitt Rubinfeld
2008 — ch.
Linearity Testing/Testing Hadamard Codes.
Encyclopedia of Algorithms
Ronitt Rubinfeld
2008 J jnl
Non-abelian homomorphism testing, and distributions close to their self-convolutions.
Random Struct. Algorithms
Michael Ben-Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld
2008 — ed.
Sublinear Algorithms, 17.08. - 22.08.2008
Sublinear Algorithms
Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler
2007 J jnl
Sublinear Algorithms for Approximating String Compressibility
CoRR
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith
2007 — conf
Sublinear Algorithms for Approximating String Compressibility.
APPROX-RANDOM
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith
2007 J jnl
Testing Halfspaces.
Electron. Colloquium Comput. Complex.
Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio
2007 A* conf
Testing for Concise Representations.
FOCS
Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan
2007 J jnl
Testing for Concise Representations.
Electron. Colloquium Comput. Complex.
Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan
2007 A* conf
Testing k-wise and almost k-wise independence.
STOC
Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie
2006 — ed.
Sublinear Algorithms, 17.07. - 22.07.2005
Sublinear Algorithms
Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler
2006 J jnl
Tolerant property testing and distance approximation.
J. Comput. Syst. Sci.
Michal Parnas, Dana Ron, Ronitt Rubinfeld
2005 — conf
05291 Abstracts Collection -- Sublinear Algorithms.
Sublinear Algorithms
Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler
2005 J jnl
Approximating the Minimum Spanning Tree Weight in Sublinear Time.
SIAM J. Comput.
Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan
2005 J jnl
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time.
SIAM J. Comput.
Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler
2005 J jnl
Fast approximate PCPs for multidimensional bin-packing problems.
Inf. Comput.
Tugkan Batu, Ronitt Rubinfeld, Patrick White
2005 J jnl
Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size
Electron. Colloquium Comput. Complex.
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam D. Smith
2005 A* conf
Testing monotone high-dimensional distributions.
STOC
Ronitt Rubinfeld, Rocco A. Servedio
2005 J jnl
The Complexity of Approximating the Entropy.
SIAM J. Comput.
Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld
2004 J jnl
Fast approximate probabilistically checkable proofs.
Inf. Comput.
Funda Ergün, Ravi Kumar, Ronitt Rubinfeld
2004 — conf
Non-Abelian Homomorphism Testing, and Distributions Close to Their Self-convolutions.
APPROX-RANDOM
Michael Ben-Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld
2004 J jnl
Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions
Electron. Colloquium Comput. Complex.
Michael Ben-Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld
2004 A* conf
Sublinear algorithms for testing monotone and unimodal distributions.
STOC
Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld
2004 A* conf
The Bloomier filter: an efficient data structure for static support lookup tables.
SODA
Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, Ayellet Tal
2004 J jnl
Tolerant Property Testing and Distance Approximation
Electron. Colloquium Comput. Complex.
Michal Parnas, Dana Ron, Ronitt Rubinfeld
2003 A* conf
A sublinear algorithm for weakly approximating edit distance.
STOC
Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami
2003 J jnl
Algorithms column: sublinear time algorithms.
SIGACT News
Ravi Kumar, Ronitt Rubinfeld
2003 J jnl
On Testing Convexity and Submodularity.
SIAM J. Comput.
Michal Parnas, Dana Ron, Ronitt Rubinfeld
2003 A* conf
Sublinear-time approximation of Euclidean minimum spanning tree.
SODA
Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler
2003 J jnl
Testing membership in parenthesis languages.
Random Struct. Algorithms
Michal Parnas, Dana Ron, Ronitt Rubinfeld
2002 A* conf
Monotonicity testing over general poset domains.
STOC
Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky
2002 — conf
On Testing Convexity and Submodularity.
RANDOM
Michal Parnas, Dana Ron, Ronitt Rubinfeld
2002 A conf
The Complexity of Approximating the Entropy.
CCC
Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld
2002 A* conf
The complexity of approximating entropy.
STOC
Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld
2001 A* conf
Approximating the Minimum Spanning Tree Weight in Sublinear Time.
ICALP
Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan
2001 J jnl
Checking Approximate Computations of Polynomials and Functional Equations.
SIAM J. Comput.
Funda Ergün, Ravi Kumar, Ronitt Rubinfeld
2001 A* conf
Selective private function evaluation with applications to private statistics.
PODC
Ran Canetti, Yuval Ishai, Ravi Kumar, Michael K. Reiter, Ronitt Rubinfeld, Rebecca N. Wright
2001 — conf
Testing Parenthesis Languages.
RANDOM-APPROX
Michal Parnas, Dana Ron, Ronitt Rubinfeld
2001 A* conf
Testing Random Variables for Independence and Identity.
FOCS
Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, Patrick White
2000 J jnl
Learning Polynomials with Queries: The Highly Noisy Case.
SIAM J. Discret. Math.
Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan
2000 A* conf
Random walks with "back buttons" (extended abstract).
STOC
Ronald Fagin, Anna R. Karlin, Jon M. Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, Andrew Tomkins
2000 J jnl
Spot-Checkers.
J. Comput. Syst. Sci.
Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan
2000 A* conf
Testing that distributions are close.
FOCS
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
1999 — conf
Fast Approximate PCPs for Multidimensional Bin-Packing Problems.
RANDOM-APPROX
Tugkan Batu, Ronitt Rubinfeld, Patrick White
1999 A* conf
Fast Approximate PCPs.
STOC
Funda Ergün, Ravi Kumar, Ronitt Rubinfeld
1999 J jnl
On the Robustness of Functional Equations.
SIAM J. Comput.
Ronitt Rubinfeld
1998 J jnl
Learning Polynomials with Queries - The Highly Noisy Case.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan
1998 J jnl
Reconstructing Algebraic Functions from Mixed Data.
SIAM J. Comput.
Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan
1998 A* conf
Spot-Checkers.
STOC
Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan
1997 J jnl
Efficient Learning of Typical Finite Automata from Random Walks.
Inf. Comput.
Yoav Freund, Michael J. Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
1997 J jnl
Exactly Learning Automata of Small Cover Time.
Mach. Learn.
Dana Ron, Ronitt Rubinfeld
1997 A* conf
Learning Distributions from Random Walks.
COLT
Funda Ergün, Ravi Kumar, Ronitt Rubinfeld
1996 A* conf
Approximate Checking of Polynomials and Functional Equations (extended abstract).
FOCS
Funda Ergün, Ravi Kumar, Ronitt Rubinfeld
1996 J jnl
Designing Checkers for Programs that Run in Parallel.
Algorithmica
Ronitt Rubinfeld
1996 J jnl
Robust Characterizations of Polynomials with Applications to Program Testing.
SIAM J. Comput.
Ronitt Rubinfeld, Madhu Sudan
1996 A* conf
Short Paths in Expander Graphs.
FOCS
Jon M. Kleinberg, Ronitt Rubinfeld
1995 A* conf
Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries.
FOCS
Yoav Freund, Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire
1995 A* conf
Exactly Learning Automata with Small Cover Time.
COLT
Dana Ron, Ronitt Rubinfeld
1995 J jnl
Learning Fallible Deterministic Finite Automata.
Mach. Learn.
Dana Ron, Ronitt Rubinfeld
1995 A* conf
Learning Polynomials with Queries: The Highly Noisy Case.
FOCS
Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan
1995 A* conf
On Learning Bounded-Width Branching Programs.
COLT
Funda Ergün, Ravi Kumar, Ronitt Rubinfeld
1994 — conf
A new modular interpolation algorithm for factoring multivariate polynominals.
ANTS
Ronitt Rubinfeld, Richard Zippel
1994 A* conf
On the learnability of discrete distributions.
STOC
Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
1994 A* conf
On the robustness of functional equations
FOCS
Ronitt Rubinfeld
1993 A* conf
Efficient learning of typical finite automata from random walks.
STOC
Yoav Freund, Michael J. Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
1993 A* conf
Learning Fallible Finite State Automata.
COLT
Dana Ron, Ronitt Rubinfeld
1993 J jnl
Self-Testing/Correcting with Applications to Numerical Problems.
J. Comput. Syst. Sci.
Manuel Blum, Michael Luby, Ronitt Rubinfeld
1992 J jnl
Batch Checking with Applications to Linear Functions.
Inf. Process. Lett.
Ronitt Rubinfeld
1992 J jnl
On the Time and Space Complexity of Computation Using Write-Once Memory Or Is Pen Really Much Worse Than Pencil?
Math. Syst. Theory
Sandy Irani, Moni Naor, Ronitt Rubinfeld
1992 A* conf
Reconstructing Algebraic Functions from Mixed Data
FOCS
Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan
1992 A* conf
Self-Testing Polynomial Functions Efficiently and Over Rational Domains.
SODA
Ronitt Rubinfeld, Madhu Sudan
1991 J jnl
A Competitive 2-Server Algorithm.
Inf. Process. Lett.
Sandy Irani, Ronitt Rubinfeld
1991 A* conf
Interactive Proofs with Space Bounded Provers.
CRYPTO
Joe Kilian, Ronitt Rubinfeld
1991 A* conf
Self-Testing/Correcting for Polynomials and for Approximate Functions
STOC
Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson
1990 A* conf
Self-Testing/Correcting with Applications to Numerical Problems
STOC
Manuel Blum, Michael Luby, Ronitt Rubinfeld
1990 J jnl
The Cover Time of a Regular Expander is O(n log n).
Inf. Process. Lett.
Ronitt Rubinfeld
1989 — conf
Program Result Checking against Adaptive Programs and in Cryptographic Settings.
Distributed Computing And Cryptography
Manuel Blum, Michael Luby, Ronitt Rubinfeld
1989 J jnl
Reversing Trains: A Turn of the Century Sorting Problem.
J. Algorithms
Nancy M. Amato, Manuel Blum, Sandy Irani, Ronitt Rubinfeld
1987 J jnl
Automatic evaluation of two-fingered grips.
IEEE J. Robotics Autom.
James Barber, Richard A. Volz, Rajiv S. Desai, Ronitt Rubinfeld, Brian Schipper, Jan D. Wolter
1986 A* conf
Automatic two-fingered grip selection.
ICRA
James Barber, Richard A. Volz, Rajiv S. Desai, Ronitt Rubinfeld, Brian Schipper, Jan D. Wolter