25 citations · 49 across the 16 of their papers we have counts for
23 papers · 1 filter
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…
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…
Testing bounded arboricity
Talya Eden, Reut Levi, Dana Ron
In this paper we consider the problem of testing whether a graph has bounded arboricity. The family of graphs with bounded arboricity includes, among others, bounded-degree graphs,…
On Approximating the Number of -cliques in Sublinear Time
Talya Eden, Dana Ron, C. Seshadhri
We study the problem of approximating the number of -cliques in a graph when given query access to the graph. We consider the standard query model for general graphs via (1) deg…
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism
Eric Blais, Clément L. Canonne, Talya Eden +2
A function is a -junta if it depends on at most of its variables. We consider the problem of tolerant testing of -juntas, where the test…
A Local Algorithm for Constructing Spanners in Minor-Free Graphs
Reut Levi, Dana Ron, Ronitt Rubinfeld
Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider this problem in the setting of local algorithms: one wants to quickly determine…
Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection
Talya Eden, Dana Ron, C. Seshadhri
We revisit the classic problem of estimating the degree distribution moments of an undirected graph. Consider an undirected graph with vertices, and define (for $s >…
Approximately Counting Triangles in Sublinear Time
Talya Eden, Amit Levi, Dana Ron +1
We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in both theory and practice, but all existing algorithms read th…
The Power of an Example: Hidden Set Size Approximation Using Group Queries and Conditional Sampling
Dana Ron, Gilad Tsur
We study a basic problem of approximating the size of an unknown set in a known universe . We consider two versions of the problem. In both versions the algorithm can specif…
Best of Two Local Models: Local Centralized and Local Distributed Algorithms
Guy Even, Moti Medina, Dana Ron
We consider two models of computation: centralized local algorithms and local distributed algorithms. Algorithms in one model are adapted to the other model to obtain improved algo…
Local Algorithms for Sparse Spanning Graphs
Reut Levi, Dana Ron, Ronitt Rubinfeld
Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider a relaxed version of this problem in the setting of local algorithms. The relaxa…
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…
A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support
Akashnil Dutta, Reut Levi, Dana Ron +1
We present a simple adaptation of the Lempel Ziv 78' (LZ78) compression scheme ({\em IEEE Transactions on Information Theory, 1978}) that supports efficient random access to the in…
Testing probability distributions using conditional samples
Clement Canonne, Dana Ron, Rocco A. Servedio
We study a new framework for property testing of probability distributions, by considering distribution testing algorithms that have access to a conditional sampling oracle.* This…
A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size
Krzysztof Onak, Dana Ron, Michal Rosen +1
We give a nearly optimal sublinear-time algorithm for approximating the size of a minimum vertex cover in a graph G. The algorithm may query the degree deg(v) of any vertex v of it…
Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity
Dana Ron, Ronitt Rubinfeld, Muli Safra +1
The {\em Total Influence} ({\em Average Sensitivity) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influence of a monot…
Finding Cycles and Trees in Sublinear Time
Artur Czumaj, Oded Goldreich, Dana Ron +3
We present sublinear-time (randomized) algorithms for finding simple cycles of length at least and tree-minors in bounded-degree graphs. The complexity of these algorithm…
Sublinear Algorithms for Approximating String Compressibility
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld +1
We raise the question of approximating the compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popul…