Papers by Dana Ron

All papers are in PDF

On Approximating the Number of Relevant Variables in a Function 
     With: Gilad Tsur 
     To appear: Proceedings of Random 2011
     20 pages, 305,526 bytes
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity 
     With: Ronit Rubinfeld, Muli Safra and Omrin Weinstein
     To appear: Proceedings of Random 2011
     15 pages, 232,936 bytes
Testing Properties of Collections of Distributions 
     With: Reut Levi and Ronit Rubinfeld
     Appeared: Proceedings of ICS 2011
     44 pages, 528,763 bytes
Testing Properties of Sparse Images 
     With: Gilad Tsur 
     Appeared: Proceedings of FOCS 2010
     42 pages, 407,848 bytes
Distribution-Free Testing of Monomials with a Sublinear Number of Queries 
     With: Elya Dolev 
     Appeared: Proceedings of RANDOM 2010
     18 pages, 209,133 bytes
Testing Computability by Width Two OBDD 
     With: Gilad Tsur 
     Appeared: Part of this work appeared in the proceedings of RANDOM 2009
     27 pages, 347,672 bytes
Algorithmic and Analysis Techniques in Property Testing 
     84 pages, 773,543  bytes
     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: Proceedings of SODA 2010
     43 pages, 364,483 bytes
Property Testing: A Learning Theory Perspective 
     63 pages, 613,943 bytes
     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: Proceedings of RANDOM 2009
     62 pages, 559,763 bytes
On Proximity Oblivious Testing 
     With: Oded Goldreich
     Appeared: Proceedings of STOC 2009
     34 pages, 187,200 bytes
Finding a Dense-Core in Jellyfish graphs 
     With: Mira Gonen, Udi Weinsberg and Avishai Wool
     Appeared: Computer Networks
     17 pages, 186,445 bytes
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
     23 pages, 276,962 bytes
On the Benefits of Adaptivity in Property Testing of Dense Graphs 
     With: Mira Gonen
     Appeared: Algorithmica (RANDOM 2007 special issue)
     18 pages, 256,440 bytes
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem 
     With: Sofya Raskhodnikova, Amir Shpilka, and Adam Smith
     Apppeared: SICOMP 
     22 pages, 263,362 bytes
Sublinear Algorithms for Approximating String Compressibility 
     With: Sofya Raskhodnikova, Ronitt Rubinfeld, and Adam Smith
     Apppeared: Proceedings of RANDOM 2007
     19 pages, 209,267 bytes
Approximating the Minimum Vertex Cover in Sublinear Time and a Connection to Distributed Algorithms 
     With: Michal Parnas 
     Appeared: Theoretical Computer Science
     20 pages, 223,251 bytes
Approximating the Distance to Monotonicity in High Dimensions 
     With: Shahar Fattal 
     To Appear: Transactions on Algorithms
     33 pages, 281,488 bytes
Approximating the Distance to Convexity 
     With: Shahar Fattal
     21 pages, 191,376 bytes
Scheduling with Conflicts: Online and Offline Algorithms 
     With: Guy Even, Magnus M. Halldorsson, and Lotem Kaplan
     Appeared: Journal of Scheduling
     40 pages, 394,750 bytes
Distance Approximation in Bounded-Degree and General Sparse Graphs 
     With: Sharon Marko 
     Appeared: Transactions on Algorithms 
     23 pages, 280,769 bytes
Testing Triangle-Freeness in General Graphs 
     With: Noga Alon, Tali Kaufman and Michael Krivelevich
     Appeared: SIAM Journal on Discrete Math 
     28 pages, 304,495 bytes
Approximating Average Parameters of Graphs 
     With: Oded Goldreich
     Appeared: Random Structures and Algorithms
     19 pages, 240,593 bytes
Tolerant Property Testing and Distance Approximation 
     With: Michal Parnas and Ronitt Rubinfeld.
     Appeared: JCSS
     37 pages,  665,986 bytes
Testing Polynomials over General Fields 
     With: Tali  Kaufman
     Appeared: SIAM Journal on Computing 
     24 pages, 411,589 bytes
Tight Bounds for Testing Bipartiteness in General Graphs 
     With: Tali  Kaufman and  Michael  Krivelevich
     Appeared: SIAM Journal on Computing
     38 pages, 596,048 bytes
Testing Reed Muller Codes 
     With: Noga Alon, Tali Kaufman, Michael Krivelevich and Simon Litsyn
     Appeared: IEEE Transactions on Information Theory 
     16 pages,  181,976 bytes
     (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
     28 pages, 396,716 bytes
Bounds on Linear Codes for Network Multicast 
     With: Meir Feder and Ami Tavory
     Appeared: Electronic Colloqium on Computational Complexity
     28 pages,  415,367  bytes
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
     36 pages, 595,363 bytes
Testing Juntas 
     With: Eldar Fischer, Guy Kindler, Shmuel Safra, and  Alex Samorodnitsky
     Appeared: JCSS (FOCS 02 special issue)
     35 pages, 537,719 bytes
On Testing Convexity and Submodularity 
     With: Michal Parnas and Ronitt Rubinfeld.
     Appeared: SIAM Journal on Computing 
     25 pages, 356,436 bytes
Testing Parenthesis Languages 
     With: Michal Parnas and Ronitt Rubinfeld.
     Appeared:  Random Structures and Algorithms
     36 pages, 586,580 bytes
Testing Basic Boolean Formulae 
     With: Michal Parnas and Alex Samorodnitsky.
     Appeared: SIAM Journal on Discrete Math
     29 pages, 438,211 bytes
Testing Metric Properties 
     With: Michal Parnas.
     Appeared:  Random Structures and Algorithms
     34 pages, 421,860 bytes
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
     39 pages, 457,563 bytes
Testing of Clustering 
     With: Noga Alon, Seannie Dar, and Michal Parnas.
     Appeared: SIAM Journal on Discrete Math
     26 pages, 395,812 bytes
Testing Acyclicity of Directed Graphs in Sublinear Time 
     With: Michael Bender
     Appeared: Random Structures and Algorithms 
     24 pages, 336,196 bytes
Testing the Diameter of Graphs 
     With: Michal Parnas
     Appeared: Random Structures and Algorithms
     17 pages,  291,923 bytes
On Disjoint Chains of Subsets 
     With: Eric Lehman
     Appeared: Journal of Combinatorial Theory, Series A
     7 pages,  219,097 bytes
Improved Testing Algorithms for Monotonicity 
     With: Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova,
           and Alex Samorodnitsky
     Appeared: Proceedings of RANDOM 99 
     18 pages, 332,841 bytes
Chinese Remaindering with Errors 
     With: Oded Goldreich and Madhu Sudan
     Appeared: IEEE Transactions on Information Theory
                (A preliminary version appeared in STOC99)
     16 pages, 327,222 bytes
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)
     28 pages, 499,500 bytes
Testing Problems with Sub-Learning Sample Complexity 
     With: Michael Kearns
     Appeared: Journal of Computer and System Sciences
     25 pages, 289,484 bytes
A Sublinear Bipartite Tester for Bounded Degree Graphs 
     With: Oded Goldreich
     Appeared: Combinatorica
     25 pages, 290,919 bytes
The Power of a Pebble: Exploring and Mapping Directed Graphs 
     With: Michael Bender, Antonio Fernandez, Amit Sahai, and Salil Vadhan
     Appeared: Information and Computation
     28 pages, 382,680 bytes
On Universal Learning Algorithms 
     With: Oded Goldreich
     Appeared: Information Processing Letters, 63, 1997
     7 pages, 167,246 bytes
     A Comment
Computational Sample Complexity 
     With: Scott Decatur and Oded Goldreich
     Appeared: SIAM Journal on Computing
     26 pages, 394,696 bytes
Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation 
     With: Michael Kearns
     Appeared: Neural Computation
     20 pages, 228,121 bytes
Property Testing in Bounded Degree Graphs Extended Abstract, Long Version 
     With: Oded Goldreich
     Appeared: Algorithmica
     Extended Abstract: 10 pages, 285,090 bytes
     Long Version: 44 pages, 623,999 bytes
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
     Extended Abstract: 10 pages, 232,088 bytes
     Long Version: 90 pages, 1,539,166 bytes
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
     10 pages, 196,099  bytes
Exactly Learning Automata with Small Cover Time 
     With: Ronitt Rubinfeld
     Appeared: Machine Learning (Extended abstract appeared 
               in the proceedings of COLT95)
     24 pages,  362,432 bytes
On the Learnability and Usage of Acyclic Probabilistic Finite Automata 
     With: Yoram Singer and Naftali Tishby
     To Appear in: Journal of Computer and System Sciences (Extended 
                   abstract appeared in the proceedings of COLT95)
     25 pages, 449,764 bytes
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	
     10 pages, 204,964 bytes
An Experimental and Theoretical Comparison of Model Selection Methods 
     With: Michael Kearns, Yishai Mansour, and Andrew Ng
     Appeared: Machine Learning (Extended abstract appeared in 
               the proceedings of COLT95)
     37 pages,  576,907 bytes
On Randomized One-Round Communication Complexity 
     With: Ilan Kremer and Noam Nisan
     Appeared: Computational Complexity (Extended abstract appeared in
                   the proceedings of STOC95)
     29 pages, 433,537 bytes
     (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 
     10 pages, 275,216  bytes
The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length 
     With: Yoram Singer and Naftali Tishby
     Appeared: Machine Learning 1996 (Extended abstract appeared 
               in the proceedings of COLT94)
     34 pages, 416,884 bytes
Learning Fallible Deterministic Finite Automata 
     With: Ronitt Rubinfeld
     Appeared: Machine Learning (Extended abstract appeared in the
               proceedings of COLT93)
     37 pages, 388,950  bytes
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 (Extended abstract appeared in the proceedings of STOC93)
     21 pages, 282,836  bytes
Agreement in the Presence of Faults on Networks of Bounded Degree 
     With: Michael Ben-Or
     Appeared: Information Processing Letters, 57, 1996
     8 pages, 174,743 bytes