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 2021Show all

2 papers · 1 filter

cs.DS2021

Approximating the Arboricity in Sublinear Time

Talya Eden, Saleet Mossel, Dana Ron

We consider the problem of approximating the arboricity of a graph , which we denote by , in sublinear time, where the arboricity of a graph is the minim…

cs.DS2021

Testing Dynamic Environments: Back to Basics

Yonatan Nakar, Dana Ron

We continue the line of work initiated by Goldreich and Ron (Journal of the ACM, 2017) on testing dynamic environments and propose to pursue a systematic study of the complexity of…