Papers by Dana Ron

All papers are in PDF

On the Possibilities and Limitations of Pseudodeterministic Algorithms 
     With: Oded Goldreich and Shafi Goldwasser 
     To Appear: Proceedings of ITCS 2013
Exponentially improved algorithms and lower bounds for testing signed majorities 
     With: Rocco Servedio 
     To Appear: Proceedings of SODA 2013
Testing Similar Means 
     With: Reut Levi and Ronitt Rubinfeld 
     Appeared: Proceedings of ICALP 2012
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, 2011
On Approximating the Number of Relevant Variables in a Function 
     With: Gilad Tsur 
     Appeared: Proceedings of Random 2011
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity 
     With: Ronit Rubinfeld, Muli Safra and Omri Weinstein
     Appeared: Proceedings of Random 2011
Testing Properties of Collections of Distributions 
     With: Reut Levi and Ronit Rubinfeld
     Appeared: Proceedings of I(T)CS 2011
Testing Properties of Sparse Images 
     With: Gilad Tsur 
     Appeared: Proceedings of FOCS 2010
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