25 citations · 49 across the 16 of their papers we have counts for
30 papers
Sample-based distance-approximation for subsequence-freeness
Omer Cohen Sidon, Dana Ron
In this work, we study the problem of approximating the distance to subsequence-freeness in the sample-based distribution-free model. For a given subsequence (word) $w = w_1 \dots…
Testing Distributions of Huge Objects
Oded Goldreich, Dana Ron
We initiate a study of a new model of property testing that is a hybrid of testing properties of distributions and testing properties of strings. Specifically, the new model refers…
The Structure of Configurations in One-Dimensional Majority Cellular Automata: From Cell Stability to Configuration Periodicity
Yonatan Nakar, Dana Ron
We study the dynamics of (synchronous) one-dimensional cellular automata with cyclical boundary conditions that evolve according to the majority rule with radius . We introduc…
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…