Papers by Dana Ron

All papers are in PDF. Note that not all version are the final (journal) versions.

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism
    With: Eric Blais, Clement Canonne, Talya Eden and Amit Levi 
Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection
    With: Talya Eden and C. Seshadhri 
The Power of an Example: Hidden Set Size Approximation Using Group Queries and Conditional Sampling
     With: Gilad Tsur 
     Appeared: ACM Transaction on Computation Theory
Approximately Counting Triangles in Sublinear Time
    With: Talya Eden, Amit Levi and C. Seshadhri 
    Appeared: Proceedings of FOCS 2015
On Sample-Based Testers
    With: Oded Goldreich 
    Appeared: Proceedings of ITCS 2015, to appear in ACM Transactions on Computation Theory
On Learning and Testing Dynamic Environments
    With: Oded Goldreich 
    Appeared: Proceedings of FOCS 2014
Local Algorithms for Sparse Spanning Graphs
     With: Reut Levi and Ronitt Rubinfeld
     Appeared: Proceedings of RANDOM 2014. Part of this work will appear in Random Structures and Algorithms
Best of two local models: local centralized and local distributed algorithms
    With: Guy Even and Moti Medina
    Appeared: Part of this work appeared in the proceedings of ESA 2014 and part will appear
              in the proceedings of ICDCN 2015
Testing probability distributions using conditional samples
    With: Clemente Cannone and Rocco Servedio
    Appeared: Proceedings of SODA 2014,  SIAM Journal on Computing
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
     With: Reut Levi 
     Appeared: Proceedings of ICALP 2013, ACM Transactions on Algorithms
A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support
     With: Akashnil Dutta, Reut Levi and Ronitt Rubinfeld
     Appeared: Proceedings of DCC 2013
On the Possibilities and Limitations of Pseudodeterministic Algorithms
     With: Oded Goldreich and Shafi Goldwasser 
     Appeared: Proceedings of ITCS 2013
Exponentially improved algorithms and lower bounds for testing signed majorities
     With: Rocco Servedio 
     Appeared: Proceedings of SODA 2013,  Algorithmica
Testing Similar Means
     With: Reut Levi and Ronitt Rubinfeld 
     Appeared: Proceedings of ICALP 2012, SIAM Journal on Discrete Math
A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size
     With: Krzysztof Onak, Michal Rosen and Ronitt Rubinfeld
     Appeared: Proceedings of SODA 2012
Testing Eulerianity and Connectivity in Directed Sparse Graphs
     With: Yaron Orenstein 
     Appeared: Theoretical Computer Science
On Approximating the Number of Relevant Variables in a Function
     With: Gilad Tsur 
     Appeared: ACM Transaction on Computation Theory
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity
     With: Ronit Rubinfeld, Muli Safra, Alex Samorodnitsky and Omri Weinstein
     Appeared: ACM Transaction on Computation Theory
Testing Properties of Collections of Distributions
     With: Reut Levi and Ronitt Rubinfeld
     Appeared: Theory of Computing 
Testing Properties of Sparse Images
     With: Gilad Tsur 
     Appeared: Proceedings of FOCS 2010,  ACM Transactions on Algorithms
Distribution-Free Testing of Monomials with a Sublinear Number of Queries
     With: Elya Dolev 
     Appeared: Theory of Computing
Testing Computability by Width Two OBDD
     With: Gilad Tsur 
     Appeared: Theoretical Computer Science
Algorithmic and Analysis Techniques in Property Testing
     Appeared: Foundations and Trends in Theoretical Computer Science, 2010.
    The Now Publisher version.
Counting Stars and Other Small Subgraphs in Sublinear Time
     With: Mira Gonen and Yuval Shavitt 
     Appeared: SIAM Journal on Discrete Math
Property Testing: A Learning Theory Perspective
     Appeared: Foundations and Trends in Machine Learning, 2008.
     A printed and bound version of this article is available at a 50% discount 
     from Now Publishers. This can be obtained by entering the promotional code
     MAL001003 on the  order form  at now publishers.
Algorithmic Aspects of Property Testing in the Dense Graphs Model
     With: Oded Goldreich
     Appeared: SIAM Journal on Computing
On Proximity Oblivious Testing
     With: Oded Goldreich
     Appeared: SIAM Journal on Computing
Finding a Dense-Core in Jellyfish graphs
     With: Mira Gonen, Udi Weinsberg and Avishai Wool
     Appeared: Computer Networks
Comparing the strength of query types in property testing: The case of testing $k$-colorability
     With: Ido Ben-Eliezer, Tali Kaufman, and Michael Krivelevich
     Appeared: Proceedings of SODA 2008 (to appear in Computational Complexity)
On the Benefits of Adaptivity in Property Testing of Dense Graphs
     With: Mira Gonen
     Appeared: Algorithmica (RANDOM 2007 special issue)
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
     With: Sofya Raskhodnikova, Amir Shpilka, and Adam Smith
     Apppeared: SIAM Journal on Computing
Sublinear Algorithms for Approximating String Compressibility
     With: Sofya Raskhodnikova, Ronitt Rubinfeld, and Adam Smith
     Apppeared: Proceedings of RANDOM 2007 (to appear in Algorithmica)
Approximating the Minimum Vertex Cover in Sublinear Time and a Connection to Distributed Algorithms
     With: Michal Parnas 
     Appeared: Theoretical Computer Science
Approximating the Distance to Monotonicity in High Dimensions
     With: Shahar Fattal 
     To Appear: Transactions on Algorithms
Approximating the Distance to Convexity
     With: Shahar Fattal
Scheduling with Conflicts: Online and Offline Algorithms
     With: Guy Even, Magnus M. Halldorsson, and Lotem Kaplan
     Appeared: Journal of Scheduling
Distance Approximation in Bounded-Degree and General Sparse Graphs
     With: Sharon Marko 
     Appeared: Transactions on Algorithms 
Testing Triangle-Freeness in General Graphs
     With: Noga Alon, Tali Kaufman and Michael Krivelevich
     Appeared: SIAM Journal on Discrete Math 
Approximating Average Parameters of Graphs
     With: Oded Goldreich
     Appeared: Random Structures and Algorithms
Tolerant Property Testing and Distance Approximation
     With: Michal Parnas and Ronitt Rubinfeld.
     Appeared: Journal of Computer and System Sciences
Testing Polynomials over General Fields
     With: Tali  Kaufman
     Appeared: SIAM Journal on Computing 
Tight Bounds for Testing Bipartiteness in General Graphs
     With: Tali  Kaufman and  Michael  Krivelevich
     Appeared: SIAM Journal on Computing
Testing Reed Muller Codes
     With: Noga Alon, Tali Kaufman, Michael Krivelevich and Simon Litsyn
     Appeared: IEEE Transactions on Information Theory 
     (Title of conference version (RANDOM 2003): Testing Low-Degree Polynomials over GF(2))
A New Conceptual Clustering Framework
     With: Nina Mishra and Ram Swaminathan,
     Appeared: Journal of Machine Learning
Bounds on Linear Codes for Network Multicast
     With: Meir Feder and Ami Tavory
     Appeared: Electronic Colloqium on Computational Complexity
Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
     With: Guy Even, Zvi Lotker and Shakhar Smorodinsky.
     Appeared: SIAM Journal on Computing
Testing Juntas
     With: Eldar Fischer, Guy Kindler, Shmuel Safra, and  Alex Samorodnitsky
     Appeared: Journal of Computer and System Sciences (FOCS 02 special issue)
On Testing Convexity and Submodularity
     With: Michal Parnas and Ronitt Rubinfeld.
     Appeared: SIAM Journal on Computing 
Testing Parenthesis Languages
     With: Michal Parnas and Ronitt Rubinfeld.
     Appeared:  Random Structures and Algorithms
Testing Basic Boolean Formulae
     With: Michal Parnas and Alex Samorodnitsky.
     Appeared: SIAM Journal on Discrete Math
Testing Metric Properties
     With: Michal Parnas.
     Appeared:  Random Structures and Algorithms
Property Testing (A Tutorial)
     Appeared: Handbook on Randomization, volume II
     Edited by: S. Rajasekaran, P. M. Pardalos, J. H. Reif, and J. D. P. Rolim
Testing of Clustering
     With: Noga Alon, Seannie Dar, and Michal Parnas.
     Appeared: SIAM Journal on Discrete Math
Testing Acyclicity of Directed Graphs in Sublinear Time
     With: Michael Bender
     Appeared: Random Structures and Algorithms 
Testing the Diameter of Graphs
     With: Michal Parnas
     Appeared: Random Structures and Algorithms
On Disjoint Chains of Subsets
     With: Eric Lehman
     Appeared: Journal of Combinatorial Theory, Series A
Improved Testing Algorithms for Monotonicity
     With: Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova,
           and Alex Samorodnitsky
     Appeared: Proceedings of RANDOM 99 
Chinese Remaindering with Errors
     With: Oded Goldreich and Madhu Sudan
     Appeared: IEEE Transactions on Information Theory
Testing Monotonicity
     With: Oded Goldreich, Shafi Goldwasser, Eric Lehman, and 
           Alex Samorodnitsky
     Appeared: Combinatorica (a preliminary (and weaker) version, 
                together with the first 3 coauthors appeared in FOCS98)
Testing Problems with Sub-Learning Sample Complexity
     With: Michael Kearns
     Appeared: Journal of Computer and System Sciences
A Sublinear Bipartite Tester for Bounded Degree Graphs
     With: Oded Goldreich
     Appeared: Combinatorica
The Power of a Pebble: Exploring and Mapping Directed Graphs
     With: Michael Bender, Antonio Fernandez, Amit Sahai, and Salil Vadhan
     Appeared: Information and Computation
On Universal Learning Algorithms
     With: Oded Goldreich
     Appeared: Information Processing Letters, 63, 1997
     A Comment
Computational Sample Complexity
     With: Scott Decatur and Oded Goldreich
     Appeared: SIAM Journal on Computing
Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation
     With: Michael Kearns
     Appeared: Neural Computation
Property Testing in Bounded Degree Graphs Extended Abstract, Long Version
     With: Oded Goldreich
     Appeared: Algorithmica
Property Testing and its Connection to Learning and Approximation Abstract, Extended Abstract Long Version
     With: Oded Goldreich and Shafi Goldwasser 
     Appeared: Journal of the ACM
Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries
     With: Yoav Freund, Michael Kearns, Yishai Mansour,  
           Ronitt Rubinfeld, and Robert Schapire
     Appeared: Proceedings of the Thirty-Sixth Annual Symposium on 
               Foundations of Computer Science (FOCS), 1995
Exactly Learning Automata with Small Cover Time
     With: Ronitt Rubinfeld
     Appeared: Machine Learning 
On the Learnability and Usage of Acyclic Probabilistic Finite Automata
     With: Yoram Singer and Naftali Tishby
     Appeare: Journal of Computer and System Sciences 
Learning to Model Sequences Generated by Switching Distributions
     With: Yoav Freund
     Appeared: Proceedings of the Eighth Annual ACM Conference on 
               Computational Learning Theory (COLT), 1995	
An Experimental and Theoretical Comparison of Model Selection Methods
     With: Michael Kearns, Yishai Mansour, and Andrew Ng
     Appeared: Machine Learning 
On Randomized One-Round Communication Complexity
     With: Ilan Kremer and Noam Nisan
     Appeared: Computational Complexity 
     (This is a corrected version of the journal paper which contained an error.)
On the Learnability of Discrete Distributions
     With: Michael Kearns, Yishai Mansour, Ronitt Rubinfeld, 
           Robert Schapire, and Linda Sellie
     Appeared: Proceedings of the Twenty-Sixth Annual ACM Symposium on 
               Theory of Computing (STOC), 1994 
The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length
     With: Yoram Singer and Naftali Tishby
     Appeared: Machine Learning 1996 
Learning Fallible Deterministic Finite Automata
     With: Ronitt Rubinfeld
     Appeared: Machine Learning 
Efficient Learning of Typical Finite Automata from Random Walks
     Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, 
     Robert Schapire, and Linda Sellie
     Appeared: Information and Computation, 138, 1997 
Agreement in the Presence of Faults on Networks of Bounded Degree
     With: Michael Ben-Or
     Appeared: Information Processing Letters, 57, 1996