3 citations · 5 across the 5 of their papers we have counts for
9 papers · 1 filter
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…
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…
Almost Optimal Bounds for Sublinear-Time Sampling of -Cliques: Sampling Cliques is Harder Than Counting
Talya Eden, Dana Ron, Will Rosenbaum
In this work, we consider the problem of sampling a -clique in a graph from an almost uniform distribution in sublinear time in the general graph query model. Specifically the a…
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…
Faster sublinear approximations of -cliques for low arboricity graphs
Talya Eden, Dana Ron, C. Seshadhri
Given query access to an undirected graph , we consider the problem of computing a -approximation of the number of -cliques in . The standard query model for gene…
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
Reut Levi, Dana Ron
Motivated by the problem of testing planarity and related properties, we study the problem of designing efficient {\em partition oracles}. A {\em partition oracle} is a procedure t…