25 citations · 49 across the 16 of their papers we have counts for
Showing 2019Show all
2 papers · 1 filter
cs.DS2019
Property testing of the Boolean and binary rank
Michal Parnas, Dana Ron, Adi Shraibman
We present algorithms for testing if a -matrix has Boolean/binary rank at most , or is -far from Boolean/binary rank (i.e., at least an -fraction of the ent…
cs.CC2019
The Arboricity Captures the Complexity of Sampling Edges
Talya Eden, Dana Ron, Will Rosenbaum
In this paper, we revisit the problem of sampling edges in an unknown graph from a distribution that is (pointwise) almost uniform over . We consider the case where…