Publications (23)
Space-efficient Local Computation Algorithms
Noga Alon, Ronitt Rubinfeld, Shai Vardi +1
Sampling Correctors
Clément Canonne, Themis Gouleakis, Ronitt Rubinfeld
Local Computation Algorithms for Graphs of Non-Constant Degrees
Reut Levi, Ronitt Rubinfeld, Anak Yodpinyanee
Approximating the noise sensitivity of a monotone Boolean function
Ronitt Rubinfeld, Arsen Vasilyan
Testing probability distributions underlying aggregated data
Clément Canonne, Ronitt Rubinfeld
Local reconstructors and tolerant testers for connectivity and diameter
Andrea Campagna, Alan Guo, Ronitt Rubinfeld
A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness
Sheela Devadas, Ronitt Rubinfeld
A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size
Krzysztof Onak, Dana Ron, Michal Rosen +1
Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity
Dana Ron, Ronitt Rubinfeld, Muli Safra +1
Testing Mixtures of Discrete Distributions
Maryam Aliakbarpour, Ravi Kumar, Ronitt Rubinfeld
Set Cover in Sub-linear Time
Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld +2
Towards Testing Monotonicity of Distributions Over General Posets
Maryam Aliakbarpour, Themis Gouleakis, John Peebles +2
Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation
Maryam Aliakbarpour, Amartya Shankha Biswas, Themistoklis Gouleakis +3
Differentially Private Identity and Closeness Testing of Discrete Distributions
Maryam Aliakbarpour, Ilias Diakonikolas, Ronitt Rubinfeld
Testing Closeness of Discrete Distributions
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld +2
Constructing Near Spanning Trees with Few Local Inspections
Reut Levi, Guy Moshkovitz, Dana Ron +2
Fast Local Computation Algorithms
Ronitt Rubinfeld, Gil Tamir, Shai Vardi +1
Sublinear Time Algorithms for Earth Mover's Distance
Khanh Do Ba, Huy L Nguyen, Huy N Nguyen +1
Local Computation Algorithms for Spanners
Merav Parter, Ronitt Rubinfeld, Ali Vakilian +1
Testing Shape Restrictions of Discrete Distributions
Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis +1
A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support
Akashnil Dutta, Reut Levi, Dana Ron +1
Rapid Sampling for Visualizations with Ordering Guarantees
Albert Kim, Eric Blais, Aditya Parameswaran +3
Sublinear Algorithms for Approximating String Compressibility
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld +1