activity
20072023
most citedA Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor

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

collaborators
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…