Ronitt Rubinfeld

According to our database, Ronitt Rubinfeld authored at least 145 papers between 1986 and 2025.

Collaborative distances:

• Dijkstra number of two.
• Erdős number of two.

2025

Optimal and learned algorithms for the online list update problem with Zipfian accesses.

Piotr Indyk, Isabelle Quaye, Ronitt Rubinfeld, Sandeep Silwal

Proceedings of the International Conference on Algorithmic Learning Theory, 2025

2024

New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling.

Spencer Compton, Slobodan Mitrovic, Ronitt Rubinfeld

Algorithmica, September, 2024

Stochastic Matching via In-n-Out Local Computation Algorithms.

Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Ronitt Rubinfeld

CoRR, 2024

Average-Case Local Computation Algorithms.

Amartya Shankha Biswas, Ruidi Cao, Edward Pyne, Ronitt Rubinfeld

CoRR, 2024

Optimal Algorithms for Augmented Testing of Discrete Distributions.

Maryam Aliakbarpour, Piotr Indyk, Ronitt Rubinfeld, Sandeep Silwal

Proceedings of the Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, 2024

Locally Computing Edge Orientations.

Slobodan Mitrovic, Ronitt Rubinfeld, Mihir Singhal

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

From Big Data Theory to Big Data Practice (Dagstuhl Seminar 23071).

Martin Farach-Colton, Fabian Daniel Kuhn, Ronitt Rubinfeld, Przemyslaw Uznanski

Dagstuhl Reports, February, 2023

Testing Distributional Assumptions of Learning Algorithms.

Ronitt Rubinfeld, Arsen Vasilyan

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Testing Tail Weight of a Distribution Via Hazard Rate.

Maryam Aliakbarpour, Amartya Shankha Biswas, Kavya Ravichandran, Ronitt Rubinfeld

Proceedings of the International Conference on Algorithmic Learning Theory, 2023

2022

Properly learning monotone functions via local reconstruction.

Jane Lange, Ronitt Rubinfeld, Arsen Vasilyan

CoRR, 2022

Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks.

Anders Aamand, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer, Sandeep Silwal, Tal Wagner

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Local Access to Random Walks.

Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Triangle and Four Cycle Counting with Predictions in Graph Streams.

Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang

Proceedings of the Tenth International Conference on Learning Representations, 2022

Properly learning monotone functions via local correction.

Jane Lange, Ronitt Rubinfeld, Arsen Vasilyan

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Massively Parallel Algorithms for Small Subgraph Counting.

Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Ronitt Rubinfeld, Slobodan Mitrovic

Proceedings of the Approximation, 2022

Online Page Migration with ML Advice.

Piotr Indyk, Frederik Mallmann-Trenn, Slobodan Mitrovic, Ronitt Rubinfeld

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Learning-based Support Estimation in Sublinear Time.

Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner

Proceedings of the 9th International Conference on Learning Representations, 2021

Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees.

Stephen Macke, Maryam Aliakbarpour, Ilias Diakonikolas, Aditya G. Parameswaran, Ronitt Rubinfeld

Proceedings of the 37th IEEE International Conference on Data Engineering, 2021

Sampling Multiple Edges Efficiently.

Talya Eden, Saleet Mossel, Ronitt Rubinfeld

Proceedings of the Approximation, 2021

Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time.

Amartya Shankha Biswas, Talya Eden, Ronitt Rubinfeld

Proceedings of the Approximation, 2021

2020

Amortized Edge Sampling.

Talya Eden, Saleet Mossel, Ronitt Rubinfeld

CoRR, 2020

Parallel Algorithms for Small Subgraph Counting.

Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Slobodan Mitrovic, Ronitt Rubinfeld

CoRR, 2020

Local Algorithms for Sparse Spanning Graphs.

Reut Levi, Dana Ron, Ronitt Rubinfeld

Algorithmica, 2020

Improved Local Computation Algorithm for Set Cover via Sparsification.

Christoph Grunau, Slobodan Mitrovic, Ronitt Rubinfeld, Ali Vakilian

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples.

Ronitt Rubinfeld, Arsen Vasilyan

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Local Access to Huge Random Objects Through Partial Sampling.

Amartya Shankha Biswas, Ronitt Rubinfeld, Anak Yodpinyanee

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Local Computation Algorithms.

Ronitt Rubinfeld

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Private Testing of Distributions via Sample Permutations.

Maryam Aliakbarpour, Ilias Diakonikolas, Daniel Kane, Ronitt Rubinfeld

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Local Computation Algorithms for Spanners.

Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Towards Testing Monotonicity of Distributions Over General Posets.

Maryam Aliakbarpour, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee

Proceedings of the Conference on Learning Theory, 2019

Testing Mixtures of Discrete Distributions.

Maryam Aliakbarpour, Ravi Kumar, Ronitt Rubinfeld

Proceedings of the Conference on Learning Theory, 2019

Approximating the Noise Sensitivity of a Monotone Boolean Function.

Ronitt Rubinfeld, Arsen Vasilyan

Proceedings of the Approximation, 2019

2018

Sampling Correctors.

Clément L. Canonne, Themis Gouleakis, Ronitt Rubinfeld

SIAM J. Comput., 2018

Testing Shape Restrictions of Discrete Distributions.

Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, Ronitt Rubinfeld

Theory Comput. Syst., 2018

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover.

Mohsen Ghaffari, Themis Gouleakis, Slobodan Mitrovic, Ronitt Rubinfeld

CoRR, 2018

Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling.

Maryam Aliakbarpour, Amartya Shankha Biswas, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee

Algorithmica, 2018

Set Cover in Sub-linear Time.

Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover.

Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, Ronitt Rubinfeld

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Differentially Private Identity and Equivalence Testing of Discrete Distributions.

Maryam Aliakbarpour, Ilias Diakonikolas, Ronitt Rubinfeld

Proceedings of the 35th International Conference on Machine Learning, 2018

2017

I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making.

Sajjadur Rahman, Maryam Aliakbarpour, Hidy Kong, Eric Blais, Karrie Karahalios, Aditya G. Parameswaran, Ronitt Rubinfeld

Proc. VLDB Endow., 2017

Local-Access Generators for Basic Random Graph Models.

Amartya Shankha Biswas, Ronitt Rubinfeld, Anak Yodpinyanee

CoRR, 2017

Differentially Private Identity and Closeness Testing of Discrete Distributions.

Maryam Aliakbarpour, Ilias Diakonikolas, Ronitt Rubinfeld

CoRR, 2017

Local Computation Algorithms for Graphs of Non-constant Degrees.

Reut Levi, Ronitt Rubinfeld, Anak Yodpinyanee

Algorithmica, 2017

Local Computation Algorithms (Invited Talk).

Ronitt Rubinfeld

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Can We Locally Compute Sparse Connected Subgraphs?

Ronitt Rubinfeld

Proceedings of the Computer Science - Theory and Applications, 2017

Fractional Set Cover in the Streaming Model.

Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan R. Ullman, Ali Vakilian, Anak Yodpinyanee

Proceedings of the Approximation, 2017

2016

Linearity Testing/Testing Hadamard Codes.

Sofya Raskhodnikova, Ronitt Rubinfeld

Encyclopedia of Algorithms, 2016

A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness.

Sheela Devadas, Ronitt Rubinfeld

Theory Comput. Syst., 2016

Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation.

Maryam Aliakbarpour, Amartya Shankha Biswas, Themistoklis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee

CoRR, 2016

Learning and Testing Junta Distributions.

Maryam Aliakbarpour, Eric Blais, Ronitt Rubinfeld

Proceedings of the 29th Conference on Learning Theory, 2016

A Local Algorithm for Constructing Spanners in Minor-Free Graphs.

Reut Levi, Dana Ron, Ronitt Rubinfeld

Proceedings of the Approximation, 2016

Something for (Almost) Nothing: New Advances in Sublinear-Time Algorithms.

Ronitt Rubinfeld, Eric Blais

Proceedings of the Handbook of Big Data., 2016

2015

Rapid Sampling for Visualizations with Ordering Guarantees.

Albert Kim, Eric Blais, Aditya G. Parameswaran, Piotr Indyk, Samuel Madden, Ronitt Rubinfeld

Proc. VLDB Endow., 2015

Constructing Near Spanning Trees with Few Local Inspections.

Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira

Electron. Colloquium Comput. Complex., 2015

Brief Announcement: Local Computation Algorithms for Graphs of Non-Constant Degrees.

Reut Levi, Ronitt Rubinfeld, Anak Yodpinyanee

Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

Erratum for: Approximating and Testing <i>k</i>-Histogram Distributions in Sub-linear Time.

Piotr Indyk, Reut Levi, Ronitt Rubinfeld

Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

2014

Testing probability distributions underlying aggregated data.

Clément L. Canonne, Ronitt Rubinfeld

Electron. Colloquium Comput. Complex., 2014

2013

Robust characterizations of <i>k</i>-wise independence over product spaces and related testing results.

Ronitt Rubinfeld, Ning Xie

Random Struct. Algorithms, 2013

Testing Closeness of Discrete Distributions.

Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White

J. ACM, 2013

Sublinear Algorithms for Approximating String Compressibility.

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith

Algorithmica, 2013

A Simple Online Competitive Adaptation of Lempel-Ziv Compression with Efficient Random Access Support.

Akashnil Dutta, Reut Levi, Dana Ron, Ronitt Rubinfeld

Proceedings of the 2013 Data Compression Conference, 2013

Local Reconstructors and Tolerant Testers for Connectivity and Diameter.

Andrea Campagna, Alan Guo, Ronitt Rubinfeld

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity.

Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, Omri Weinstein

ACM Trans. Comput. Theory, 2012

Testing Similar Means.

Reut Levi, Dana Ron, Ronitt Rubinfeld

Electron. Colloquium Comput. Complex., 2012

Taming big probability distributions.

Ronitt Rubinfeld

XRDS, 2012

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

Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Space-efficient local computation algorithms.

Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Approximating and testing k-histogram distributions in sub-linear time.

Piotr Indyk, Reut Levi, Ronitt Rubinfeld

Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

2011

Sublinear Time Algorithms for Earth Mover's Distance.

Khanh Do Ba, Huy L. Nguyen, Huy N. Nguyen, Ronitt Rubinfeld

Theory Comput. Syst., 2011

Sublinear Time Algorithms.

Ronitt Rubinfeld, Asaf Shapira

Electron. Colloquium Comput. Complex., 2011

Approximating and Testing <i>k</i>-Histogram Distributions in Sub-linear time.

Piotr Indyk, Reut Levi, Ronitt Rubinfeld

Electron. Colloquium Comput. Complex., 2011

Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity

Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein

CoRR, 2011

Fast Local Computation Algorithms.

Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie

Proceedings of the Innovations in Computer Science, 2011

Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity.

Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Testing Halfspaces.

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio

SIAM J. Comput., 2010

A local decision test for sparse polynomials.

Elena Grigorescu, Kyomin Jung, Ronitt Rubinfeld

Inf. Process. Lett., 2010

Testing Properties of Collections of Distributions.

Reut Levi, Dana Ron, Ronitt Rubinfeld

Electron. Colloquium Comput. Complex., 2010

Testing monotonicity of distributions over general partial orders.

Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant

Electron. Colloquium Comput. Complex., 2010

Improved Recommendations via (More) Collaboration.

Rubi Boim, Haim Kaplan, Tova Milo, Ronitt Rubinfeld

Proceedings of the 13th International Workshop on the Web and Databases 2010, 2010

Maintaining a large matching and a small vertex cover.

Krzysztof Onak, Ronitt Rubinfeld

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Dynamic Approximate Vertex Cover and Maximum Matching.

Krzysztof Onak, Ronitt Rubinfeld

Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing (Subclasses of) Halfspaces.

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio

Proceedings of the Property Testing - Current Research and Surveys, 2010

Sublinear Algorithms in the External Memory Model.

Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld

Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing Non-uniform <i>k</i>-Wise Independent Distributions over Product Spaces.

Ronitt Rubinfeld, Ning Xie

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Testing monotone high-dimensional distributions.

Ronitt Rubinfeld, Rocco A. Servedio

Random Struct. Algorithms, 2009

External Sampling.

Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Testing ±1-weight halfspace.

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio

Proceedings of the Approximation, 2009

2008

Linearity Testing/Testing Hadamard Codes.

Ronitt Rubinfeld

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

08341 Executive Summary - Sublinear Algorithms.

Artur Czumaj, S. Muthukrishnan, Ronitt Rubinfeld, Christian Sohler

Proceedings of the Sublinear Algorithms, 17.08. - 22.08.2008, 2008

08341 Abstracts Collection - Sublinear Algorithms.

Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler

Proceedings of the Sublinear Algorithms, 17.08. - 22.08.2008, 2008

2007

Testing for Concise Representations.

Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan

Electron. Colloquium Comput. Complex., 2007

Testing k-wise and almost k-wise independence.

Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

Tolerant property testing and distance approximation.

Michal Parnas, Dana Ron, Ronitt Rubinfeld

J. Comput. Syst. Sci., 2006

2005

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time.

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler

SIAM J. Comput., 2005

Approximating the Minimum Spanning Tree Weight in Sublinear Time.

Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan

SIAM J. Comput., 2005

The Complexity of Approximating the Entropy.

Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld

SIAM J. Comput., 2005

Fast approximate PCPs for multidimensional bin-packing problems.

Tugkan Batu, Ronitt Rubinfeld, Patrick White

Inf. Comput., 2005

Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam D. Smith

Electron. Colloquium Comput. Complex., 2005

05291 Abstracts Collection -- Sublinear Algorithms.

Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler

Proceedings of the Sublinear Algorithms, 17.07. - 22.07.2005, 2005

2004

Fast approximate probabilistically checkable proofs.

Funda Ergün, Ravi Kumar, Ronitt Rubinfeld

Inf. Comput., 2004

Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions

Michael Ben-Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld

Electron. Colloquium Comput. Complex., 2004

Sublinear algorithms for testing monotone and unimodal distributions.

Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

The Bloomier filter: an efficient data structure for static support lookup tables.

Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, Ayellet Tal

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

2003

Algorithms column: sublinear time algorithms.

Ravi Kumar, Ronitt Rubinfeld

SIGACT News, 2003

On Testing Convexity and Submodularity.

Michal Parnas, Dana Ron, Ronitt Rubinfeld

SIAM J. Comput., 2003

Testing membership in parenthesis languages.

Michal Parnas, Dana Ron, Ronitt Rubinfeld

Random Struct. Algorithms, 2003

A sublinear algorithm for weakly approximating edit distance.

Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Sublinear-time approximation of Euclidean minimum spanning tree.

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

2002

Monotonicity testing over general poset domains.

Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001

Checking Approximate Computations of Polynomials and Functional Equations.

Funda Ergün, Ravi Kumar, Ronitt Rubinfeld

SIAM J. Comput., 2001

Testing Parenthesis Languages.

Michal Parnas, Dana Ron, Ronitt Rubinfeld

Proceedings of the Approximation, 2001

Selective private function evaluation with applications to private statistics.

Ran Canetti, Yuval Ishai, Ravi Kumar, Michael K. Reiter, Ronitt Rubinfeld, Rebecca N. Wright

Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, 2001

Testing Random Variables for Independence and Identity.

Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, Patrick White

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Spot-Checkers.

Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan

J. Comput. Syst. Sci., 2000

Random walks with "back buttons" (extended abstract).

Ronald Fagin, Anna R. Karlin, Jon M. Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, Andrew Tomkins

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Testing that distributions are close.

Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999

On the Robustness of Functional Equations.

Ronitt Rubinfeld

SIAM J. Comput., 1999

Fast Approximate PCPs.

Funda Ergün, Ravi Kumar, Ronitt Rubinfeld

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998

Reconstructing Algebraic Functions from Mixed Data.

Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan

SIAM J. Comput., 1998

Learning Polynomials with Queries - The Highly Noisy Case.

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan

Electron. Colloquium Comput. Complex., 1998

1997

Exactly Learning Automata of Small Cover Time.

Dana Ron, Ronitt Rubinfeld

Mach. Learn., 1997

Efficient Learning of Typical Finite Automata from Random Walks.

Yoav Freund, Michael J. Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie

Inf. Comput., 1997

Learning Distributions from Random Walks.

Funda Ergün, Ravi Kumar, Ronitt Rubinfeld

Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997

1996

Robust Characterizations of Polynomials with Applications to Program Testing.

Ronitt Rubinfeld, Madhu Sudan

SIAM J. Comput., 1996

Designing Checkers for Programs that Run in Parallel.

Ronitt Rubinfeld

Algorithmica, 1996

Short Paths in Expander Graphs.

Jon M. Kleinberg, Ronitt Rubinfeld

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Approximate Checking of Polynomials and Functional Equations (extended abstract).

Funda Ergün, Ravi Kumar, Ronitt Rubinfeld

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

Learning Fallible Deterministic Finite Automata.

Dana Ron, Ronitt Rubinfeld

Mach. Learn., 1995

Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries.

Yoav Freund, Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

On Learning Bounded-Width Branching Programs.

Funda Ergün, Ravi Kumar, Ronitt Rubinfeld

Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

1994

On the learnability of discrete distributions.

Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

A new modular interpolation algorithm for factoring multivariate polynominals.

Ronitt Rubinfeld, Richard Zippel

Proceedings of the Algorithmic Number Theory, First International Symposium, 1994

1993

Self-Testing/Correcting with Applications to Numerical Problems.

Manuel Blum, Michael Luby, Ronitt Rubinfeld

J. Comput. Syst. Sci., 1993

Learning Fallible Finite State Automata.

Dana Ron, Ronitt Rubinfeld

Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993

1992

On the Time and Space Complexity of Computation Using Write-Once Memory Or Is Pen Really Much Worse Than Pencil?

Sandy Irani, Moni Naor, Ronitt Rubinfeld

Math. Syst. Theory, 1992

Batch Checking with Applications to Linear Functions.

Ronitt Rubinfeld

Inf. Process. Lett., 1992

Self-Testing Polynomial Functions Efficiently and Over Rational Domains.

Ronitt Rubinfeld, Madhu Sudan

Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

1991

A Competitive 2-Server Algorithm.

Sandy Irani, Ronitt Rubinfeld

Inf. Process. Lett., 1991

Self-Testing/Correcting for Polynomials and for Approximate Functions

Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Interactive Proofs with Space Bounded Provers.

Joe Kilian, Ronitt Rubinfeld

Proceedings of the Advances in Cryptology, 1991

1990

The Cover Time of a Regular Expander is O(n log n).

Ronitt Rubinfeld

Inf. Process. Lett., 1990

1989

Reversing Trains: A Turn of the Century Sorting Problem.

Nancy M. Amato, Manuel Blum, Sandy Irani, Ronitt Rubinfeld

J. Algorithms, 1989

Program Result Checking against Adaptive Programs and in Cryptographic Settings.

Manuel Blum, Michael Luby, Ronitt Rubinfeld

Proceedings of the Distributed Computing And Cryptography, 1989

1987

Automatic evaluation of two-fingered grips.

James Barber, Richard A. Volz, Rajiv S. Desai, Ronitt Rubinfeld, Brian Schipper, Jan D. Wolter

IEEE J. Robotics Autom., 1987

1986

Automatic two-fingered grip selection.

James Barber, Richard A. Volz, Rajiv S. Desai, Ronitt Rubinfeld, Brian Schipper, Jan D. Wolter

Proceedings of the 1986 IEEE International Conference on Robotics and Automation, 1986