5 citations · 12 across the 7 of their papers we have counts for
3 papers · 1 filter
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…