25 citations · 49 across the 16 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.DS2016
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism
Eric Blais, Clément L. Canonne, Talya Eden +2
A function is a -junta if it depends on at most of its variables. We consider the problem of tolerant testing of -juntas, where the test…
cs.DS2016★ 5 cited
A Local Algorithm for Constructing Spanners in Minor-Free Graphs
Reut Levi, Dana Ron, Ronitt Rubinfeld
Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider this problem in the setting of local algorithms: one wants to quickly determine…
cs.DS2016★ 3 cited
Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection
Talya Eden, Dana Ron, C. Seshadhri
We revisit the classic problem of estimating the degree distribution moments of an undirected graph. Consider an undirected graph with vertices, and define (for $s >…