D. Ron

Most-cited papers

The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length
D. Ron, Y. Singer, Naftali Tishby
2005Machine-mediated learning522 citations
Semantic Scholar
Tolerant property testing and distance approximation
Michal Parnas, D. Ron, R. Rubinfeld
2006Journal of computer and system sciences (Print)232 citations Open access
Semantic Scholar
On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms
Michal Parnas, D. Ron
2005Electron. Colloquium Comput. Complex.205 citations
Semantic Scholar
Algorithmic and Analysis Techniques in Property Testing
D. Ron
2010Foundations and Trends® in Theoretical Computer Science204 citations
Semantic Scholar
Property Testing: A Learning Theory Perspective
D. Ron
2007Annual Conference Computational Learning Theory191 citations Open access
Semantic Scholar
Approximating average parameters of graphs
Oded Goldreich, D. Ron
2006International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques168 citations Open access
Semantic Scholar
Approximately Counting Triangles in Sublinear Time
T. Eden, Amit Levi, D. Ron, C. Seshadhri
2015IEEE Annual Symposium on Foundations of Computer Science154 citations Open access
Semantic Scholar
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
Sofya Raskhodnikova, D. Ron, Amir Shpilka, Adam D. Smith
2009IEEE Annual Symposium on Foundations of Computer Science149 citations
Semantic Scholar
Testing Reed-Muller codes
N. Alon, T. Kaufman, Michael Krivelevich, S. Litsyn +1 more
2005IEEE Transactions on Information Theory146 citations Open access
Semantic Scholar
Counting stars and other small subgraphs in sublinear time
Mira Gonen, D. Ron, Y. Shavitt
2010ACM-SIAM Symposium on Discrete Algorithms108 citations Open access
Semantic Scholar
Testing polynomials over general fields
T. Kaufman, D. Ron
200445th Annual IEEE Symposium on Foundations of Computer Science108 citations
Semantic Scholar
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
Krzysztof Onak, D. Ron, M. Rosen, R. Rubinfeld
2011ACM-SIAM Symposium on Discrete Algorithms105 citations
Semantic Scholar
On Approximating the Number of $k$-cliques in Sublinear Time
T. Eden, D. Ron, C. Seshadhri
2017SIAM journal on computing (Print)91 citations Open access
Semantic Scholar
Testing probability distributions using conditional samples
C. Canonne, D. Ron, R. Servedio
2012Electron. Colloquium Comput. Complex.90 citations Open access
Semantic Scholar
Scheduling with conflicts: online and offline algorithms
Guy Even, M. Halldórsson, L. Kaplan, D. Ron
2009Journal of Scheduling84 citations
Semantic Scholar
On proximity oblivious testing
Oded Goldreich, D. Ron
2009Symposium on the Theory of Computing84 citations
Semantic Scholar
Testing triangle-freeness in general graphs
N. Alon, T. Kaufman, Michael Krivelevich, D. Ron
2006ACM-SIAM Symposium on Discrete Algorithms77 citations Open access
Semantic Scholar
Testing Properties of Collections of Distributions
Reut Levi, D. Ron, R. Rubinfeld
2013Theory of Computing75 citations Open access
Semantic Scholar
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
Reut Levi, D. Ron
2013International Colloquium on Automata, Languages and Programming61 citations Open access
Semantic Scholar
Approximating the distance to properties in bounded-degree and general sparse graphs
S. Marko, D. Ron
2009TALG61 citations
Semantic Scholar
Sublinear Algorithms for Approximating String Compressibility
Sofya Raskhodnikova, D. Ron, R. Rubinfeld, Adam D. Smith
2007Algorithmica59 citations
Semantic Scholar
On Sample-Based Testers
Oded Goldreich, D. Ron
2015Information Technology Convergence and Services51 citations
Semantic Scholar
Finding cycles and trees in sublinear time
A. Czumaj, Oded Goldreich, D. Ron, C. Seshadhri +2 more
2010Random Struct. Algorithms48 citations Open access
Semantic Scholar
Provable and Practical Approximations for the Degree Distribution using Sublinear Graph Samples
T. Eden, Shweta V. Jain, Ali Pinar, D. Ron +1 more
2017The Web Conference46 citations Open access
Semantic Scholar
Faster sublinear approximation of the number of k-cliques in low-arboricity graphs
T. Eden, D. Ron, C. Seshadhri
2020ACM-SIAM Symposium on Discrete Algorithms41 citations
Semantic Scholar
On the possibilities and limitations of pseudodeterministic algorithms
Oded Goldreich, S. Goldwasser, D. Ron
2013Information Technology Convergence and Services40 citations
Semantic Scholar
Algorithmic Aspects of Property Testing in the Dense Graphs Model
Oded Goldreich, D. Ron
2009Electron. Colloquium Comput. Complex.40 citations
Semantic Scholar
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism
Eric Blais, C. Canonne, T. Eden, Amit Levi +1 more
2016ACM-SIAM Symposium on Discrete Algorithms39 citations Open access
Semantic Scholar
Testing equivalence between distributions using conditional samples
C. Canonne, D. Ron, R. Servedio
2014ACM-SIAM Symposium on Discrete Algorithms38 citations
Semantic Scholar
Distance Approximation in Bounded-Degree and General Sparse Graphs
S. Marko, D. Ron
2006International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques38 citations Open access
Semantic Scholar
Distributed Maximum Matching in Bounded Degree Graphs
Guy Even, Moti Medina, D. Ron
2014International Conference of Distributed Computing and Networking37 citations
Semantic Scholar
Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs
Guy Even, Moti Medina, D. Ron
2014Embedded Systems and Applications37 citations
Semantic Scholar
Approximating the distance to monotonicity in high dimensions
S. Fattal, D. Ron
2010TALG37 citations Open access
Semantic Scholar
Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection
T. Eden, D. Ron, C. Seshadhri
2016SIAM Journal on Discrete Mathematics36 citations
Semantic Scholar
Local Algorithms for Sparse Spanning Graphs
Reut Levi, D. Ron, R. Rubinfeld
2014Algorithmica35 citations Open access
Semantic Scholar
The Arboricity Captures the Complexity of Sampling Edges
T. Eden, D. Ron, Will Rosenbaum
2019International Colloquium on Automata, Languages and Programming31 citations
Semantic Scholar
Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection
T. Eden, D. Ron, C. Seshadhri
2016International Colloquium on Automata, Languages and Programming30 citations
Semantic Scholar
The Power of an Example
D. Ron, Gilad Tsur
2014ACM Transactions on Computation Theory29 citations
Semantic Scholar
Best of Two Local Models: Local Centralized and Local Distributed Algorithms
Guy Even, Moti Medina, D. Ron
2014arXiv.org28 citations
Semantic Scholar
Testing Bounded Arboricity
T. Eden, Reut Levi, D. Ron
2017ACM-SIAM Symposium on Discrete Algorithms24 citations Open access
Semantic Scholar
Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
Michal Parnas, D. Ron
2007Theoretical Computer Science23 citations Open access
Semantic Scholar
Open Problems in Data Streams, Property Testing, and Related Topics
P. Indyk, A. Mcgregor, Nir Ailon, N. Alon +49 more
201122 citations
Semantic Scholar
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity
D. Ron, R. Rubinfeld, S. Safra, Omri Weinstein
2011International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques21 citations
Semantic Scholar
Constructing near spanning trees with few local inspections
Reut Levi, Guy Moshkovitz, D. Ron, R. Rubinfeld +1 more
2015Random Struct. Algorithms20 citations Open access
Semantic Scholar
A Simple Online Competitive Adaptation of Lempel-Ziv Compression with Efficient Random Access Support
Akashnil Dutta, Reut Levi, D. Ron, R. Rubinfeld
2013Data Compression Conference20 citations Open access
Semantic Scholar
Testing Properties of Sparse Images
D. Ron, Gilad Tsur
2010IEEE Annual Symposium on Foundations of Computer Science18 citations Open access
Semantic Scholar
Comparing the strength of query types in property testing: the case of testing k-colorability
Ido Ben-Eliezer, T. Kaufman, Michael Krivelevich, D. Ron
2008ACM-SIAM Symposium on Discrete Algorithms18 citations
Semantic Scholar
Testing Computability by Width-Two OBDDs
D. Ron, Gilad Tsur
2009Electron. Colloquium Comput. Complex.17 citations Open access
Semantic Scholar
Distribution-Free Testing for Monomials with a Sublinear Number of Queries
E. Dolev, D. Ron
2011Theory of Computing16 citations Open access
Semantic Scholar
Property testing of planarity in the CONGEST model
Reut Levi, Moti Medina, D. Ron
2018Distributed computing15 citations Open access
Semantic Scholar