# Ronitt Rubinfeld

According to our database1, Ronitt Rubinfeld authored at least 123 papers between 1986 and 2020.

Collaborative distances:
• Dijkstra number2 of three.
• Erdős number3 of two.

## ACM Fellow

ACM Fellow 2014, "For contributions to delegated computation, sublinear time algorithms and property testing.".

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2020
Improved Local Computation Algorithm for Set Cover via Sparsification.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

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

2019
Local Computation Algorithms.
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Private Testing of Distributions via Sample Permutations.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Local Computation Algorithms for Spanners.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Towards Testing Monotonicity of Distributions Over General Posets.
Proceedings of the Conference on Learning Theory, 2019

Testing Mixtures of Discrete Distributions.
Proceedings of the Conference on Learning Theory, 2019

Approximating the Noise Sensitivity of a Monotone Boolean Function.
Proceedings of the Approximation, 2019

2018
Sampling Correctors.
SIAM J. Comput., 2018

Testing Shape Restrictions of Discrete Distributions.
Theory Comput. Syst., 2018

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

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

Set Cover in Sub-linear Time.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Differentially Private Identity and Equivalence Testing of Discrete Distributions.
Proceedings of the 35th International Conference on Machine Learning, 2018

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

Local-Access Generators for Basic Random Graph Models.
CoRR, 2017

Differentially Private Identity and Closeness Testing of Discrete Distributions.
CoRR, 2017

Local Computation Algorithms for Graphs of Non-constant Degrees.
Algorithmica, 2017

Local Computation Algorithms (Invited Talk).
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Can We Locally Compute Sparse Connected Subgraphs?
Proceedings of the Computer Science - Theory and Applications, 2017

Fractional Set Cover in the Streaming Model.
Proceedings of the Approximation, 2017

2016
Encyclopedia of Algorithms, 2016

A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness.
Theory Comput. Syst., 2016

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

Learning and Testing Junta Distributions.
Proceedings of the 29th Conference on Learning Theory, 2016

A Local Algorithm for Constructing Spanners in Minor-Free Graphs.
Proceedings of the Approximation, 2016

Something for (Almost) Nothing: New Advances in Sublinear-Time Algorithms.
Proceedings of the Handbook of Big Data., 2016

2015
Rapid Sampling for Visualizations with Ordering Guarantees.
PVLDB, 2015

Constructing Near Spanning Trees with Few Local Inspections.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Brief Announcement: Local Computation Algorithms for Graphs of Non-Constant Degrees.
Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

Erratum for: Approximating and Testing k-Histogram Distributions in Sub-linear Time.
Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

2014
Testing Similar Means.
SIAM J. Discrete Math., 2014

Testing probability distributions underlying aggregated data.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Local Algorithms for Sparse Spanning Graphs.
Proceedings of the Approximation, 2014

2013
Testing Properties of Collections of Distributions.
Theory of Computing, 2013

Robust characterizations of k-wise independence over product spaces and related testing results.
Random Struct. Algorithms, 2013

Testing Closeness of Discrete Distributions.
J. ACM, 2013

Sublinear Algorithms for Approximating String Compressibility.
Algorithmica, 2013

A Simple Online Competitive Adaptation of Lempel-Ziv Compression with Efficient Random Access Support.
Proceedings of the 2013 Data Compression Conference, 2013

Local Reconstructors and Tolerant Testers for Connectivity and Diameter.
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.
TOCT, 2012

Taming big probability distributions.

A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Space-efficient local computation algorithms.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Approximating and testing k-histogram distributions in sub-linear time.
Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

2011
Sublinear Time Algorithms.
SIAM J. Discrete Math., 2011

Sublinear Time Algorithms for Earth Mover's Distance.
Theory Comput. Syst., 2011

Approximating and Testing k-Histogram Distributions in Sub-linear time.
Electronic Colloquium on Computational Complexity (ECCC), 2011

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

Fast Local Computation Algorithms.
Proceedings of the Innovations in Computer Science, 2011

Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
A local decision test for sparse polynomials.
Inf. Process. Lett., 2010

Testing monotonicity of distributions over general partial orders.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Improved Recommendations via (More) Collaboration.
Proceedings of the 13th International Workshop on the Web and Databases 2010, 2010

Maintaining a large matching and a small vertex cover.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Dynamic Approximate Vertex Cover and Maximum Matching.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing (Subclasses of) Halfspaces.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Sublinear Algorithms in the External Memory Model.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing Non-uniform k-Wise Independent Distributions over Product Spaces.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009
Testing monotone high-dimensional distributions.
Random Struct. Algorithms, 2009

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

Testing ±1-weight halfspace.
Proceedings of the Approximation, 2009

2008
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

08341 Executive Summary - Sublinear Algorithms.
Proceedings of the Sublinear Algorithms, 17.08. - 22.08.2008, 2008

08341 Abstracts Collection - Sublinear Algorithms.
Proceedings of the Sublinear Algorithms, 17.08. - 22.08.2008, 2008

2007
Testing Halfspaces.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Testing for Concise Representations.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Testing k-wise and almost k-wise independence.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006
Tolerant property testing and distance approximation.
J. Comput. Syst. Sci., 2006

2005
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time.
SIAM J. Comput., 2005

Approximating the Minimum Spanning Tree Weight in Sublinear Time.
SIAM J. Comput., 2005

The Complexity of Approximating the Entropy.
SIAM J. Comput., 2005

Fast approximate PCPs for multidimensional bin-packing problems.
Inf. Comput., 2005

Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size
Electronic Colloquium on Computational Complexity (ECCC), 2005

05291 Abstracts Collection -- Sublinear Algorithms.
Proceedings of the Sublinear Algorithms, 17.07. - 22.07.2005, 2005

2004
Fast approximate probabilistically checkable proofs.
Inf. Comput., 2004

Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions
Electronic Colloquium on Computational Complexity (ECCC), 2004

Sublinear algorithms for testing monotone and unimodal distributions.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

The Bloomier filter: an efficient data structure for static support lookup tables.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

2003
Algorithms column: sublinear time algorithms.
SIGACT News, 2003

On Testing Convexity and Submodularity.
SIAM J. Comput., 2003

Testing membership in parenthesis languages.
Random Struct. Algorithms, 2003

A sublinear algorithm for weakly approximating edit distance.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Sublinear-time approximation of Euclidean minimum spanning tree.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

2002
Monotonicity testing over general poset domains.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001
Checking Approximate Computations of Polynomials and Functional Equations.
SIAM J. Comput., 2001

Testing Parenthesis Languages.
Proceedings of the Approximation, 2001

Selective private function evaluation with applications to private statistics.
Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, 2001

Testing Random Variables for Independence and Identity.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000
Learning Polynomials with Queries: The Highly Noisy Case.
SIAM J. Discrete Math., 2000

Spot-Checkers.
J. Comput. Syst. Sci., 2000

Random walks with "back buttons" (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Testing that distributions are close.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
On the Robustness of Functional Equations.
SIAM J. Comput., 1999

Fast Approximate PCPs.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998
Reconstructing Algebraic Functions from Mixed Data.
SIAM J. Comput., 1998

1997
Exactly Learning Automata of Small Cover Time.
Machine Learning, 1997

Efficient Learning of Typical Finite Automata from Random Walks.
Inf. Comput., 1997

Learning Distributions from Random Walks.
Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997

1996
Robust Characterizations of Polynomials with Applications to Program Testing.
SIAM J. Comput., 1996

Designing Checkers for Programs that Run in Parallel.
Algorithmica, 1996

Short Paths in Expander Graphs.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Approximate Checking of Polynomials and Functional Equations (extended abstract).
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
Learning Fallible Deterministic Finite Automata.
Machine Learning, 1995

Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

On Learning Bounded-Width Branching Programs.
Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

1994
On the learnability of discrete distributions.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

A new modular interpolation algorithm for factoring multivariate polynominals.
Proceedings of the Algorithmic Number Theory, First International Symposium, 1994

1993
Self-Testing/Correcting with Applications to Numerical Problems.
J. Comput. Syst. Sci., 1993

Learning Fallible Finite State Automata.
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?
Mathematical Systems Theory, 1992

Batch Checking with Applications to Linear Functions.
Inf. Process. Lett., 1992

Self-Testing Polynomial Functions Efficiently and Over Rational Domains.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

1991
A Competitive 2-Server Algorithm.
Inf. Process. Lett., 1991

Self-Testing/Correcting for Polynomials and for Approximate Functions
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Interactive Proofs with Space Bounded Provers.
Proceedings of the Advances in Cryptology, 1991

1990
The Cover Time of a Regular Expander is O(n log n).
Inf. Process. Lett., 1990

1989
Reversing Trains: A Turn of the Century Sorting Problem.
J. Algorithms, 1989

Program Result Checking against Adaptive Programs and in Cryptographic Settings.
Proceedings of the Distributed Computing And Cryptography, 1989

1987
Automatic evaluation of two-fingered grips.
IEEE J. Robotics and Automation, 1987

1986
Automatic two-fingered grip selection.
Proceedings of the 1986 IEEE International Conference on Robotics and Automation, 1986