3 citations · 4 across the 3 of their papers we have counts for
4 papers
Towards Testing Monotonicity of Distributions Over General Posets
Maryam Aliakbarpour, Themis Gouleakis, John Peebles +2
In this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution over a poset is monotone if, for any…
Local Computation Algorithms for Spanners
Merav Parter, Ronitt Rubinfeld, Ali Vakilian +1
A graph spanner is a fundamental graph structure that faithfully preserves the pairwise distances in the input graph up to a small multiplicative stretch. The common objective in t…
Set Cover in Sub-linear Time
Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld +2
We study the classic set cover problem from the perspective of sub-linear algorithms. Given access to a collection of sets over elements in the query model, we show that su…
Local Computation Algorithms for Graphs of Non-Constant Degrees
Reut Levi, Ronitt Rubinfeld, Anak Yodpinyanee
In the model of \emph{local computation algorithms} (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. Many recent…