Dana Ron

most citedDistributed Maximum Matching in Bounded Degree Graphs

3 citations · 4 across the 3 of their papers we have counts for

collaborators

Showing cs.DSShow all

2 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 $f : {- 1, 1}^{n} \to {- 1, 1}$ is a $k$ -junta if it depends on at most $k$ of its variables. We consider the problem of tolerant testing of $k$ -juntas, where the test…

cs.DS2014★ 1 cited

The Power of an Example: Hidden Set Size Approximation Using Group Queries and Conditional Sampling

Dana Ron, Gilad Tsur

We study a basic problem of approximating the size of an unknown set $S$ in a known universe $U$ . We consider two versions of the problem. In both versions the algorithm can specif…