 | 2009 |
|---|
| 107 |       | Oded Goldreich,
Dana Ron:
Algorithmic Aspects of Property Testing in the Dense Graphs Model.
APPROX-RANDOM 2009: 520-533 |
| 106 | | Dana Ron,
Gilad Tsur:
Testing Computability by Width Two OBDDs.
APPROX-RANDOM 2009: 686-699 |
| 105 | | Oded Goldreich,
Dana Ron:
On proximity oblivious testing.
STOC 2009: 141-150 |
| 104 | | Sharon Marko,
Dana Ron:
Approximating the distance to properties in bounded-degree and general sparse graphs.
ACM Transactions on Algorithms 5(2): (2009) |
| 103 | | Guy Even,
Magnús M. Halldórsson,
Lotem Kaplan,
Dana Ron:
Scheduling with conflicts: online and offline algorithms.
J. Scheduling 12(2): 199-224 (2009) |
| 2008 |
|---|
| 102 | | Ido Ben-Eliezer,
Tali Kaufman,
Michael Krivelevich,
Dana Ron:
Comparing the strength of query types in property testing: the case of testing k-colorability.
SODA 2008: 1213-1222 |
| 101 | | Mira Gonen,
Dana Ron,
Udi Weinsberg,
Avishai Wool:
Finding a dense-core in Jellyfish graphs.
Computer Networks 52(15): 2831-2841 (2008) |
| 100 | | Oded Goldreich,
Dana Ron:
Algorithmic Aspects of Property Testing in the Dense Graphs Model.
Electronic Colloquium on Computational Complexity (ECCC) 15(039): (2008) |
| 99 | | Oded Goldreich,
Dana Ron:
On Proximity Oblivious Testing.
Electronic Colloquium on Computational Complexity (ECCC) 15(041): (2008) |
| 98 | | Dana Ron:
Property Testing: A Learning Theory Perspective.
Foundations and Trends in Machine Learning 1(3): 307-402 (2008) |
| 97 | | Oded Goldreich,
Dana Ron:
Approximating average parameters of graphs.
Random Struct. Algorithms 32(4): 473-493 (2008) |
| 96 | | Noga Alon,
Tali Kaufman,
Michael Krivelevich,
Dana Ron:
Testing Triangle-Freeness in General Graphs.
SIAM J. Discrete Math. 22(2): 786-819 (2008) |
| 2007 |
|---|
| 95 | | Mira Gonen,
Dana Ron:
On the Benefits of Adaptivity in Property Testing of Dense Graphs.
APPROX-RANDOM 2007: 525-539 |
| 94 | | Sofya Raskhodnikova,
Dana Ron,
Ronitt Rubinfeld,
Adam Smith:
Sublinear Algorithms for Approximating String Compressibility.
APPROX-RANDOM 2007: 609-623 |
| 93 | | Dana Ron:
Property Testing: A Learning Theory Perspective.
COLT 2007: 1-2 |
| 92 | | Sofya Raskhodnikova,
Dana Ron,
Amir Shpilka,
Adam Smith:
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem.
FOCS 2007: 559-569 |
| 91 | | Mira Gonen,
Dana Ron,
Udi Weinsberg,
Avishai Wool:
Finding a Dense-Core in Jellyfish Graphs.
WAW 2007: 29-40 |
| 90 | | Sofya Raskhodnikova,
Dana Ron,
Ronitt Rubinfeld,
Adam Smith:
Sublinear Algorithms for Approximating String Compressibility
CoRR abs/0706.1084: (2007) |
| 89 | | Dana Ron,
Amir Rosenfeld,
Salil P. Vadhan:
The hardness of the Expected Decision Depth problem.
Inf. Process. Lett. 101(3): 112-118 (2007) |
| 88 | | Michal Parnas,
Dana Ron:
Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms.
Theor. Comput. Sci. 381(1-3): 183-196 (2007) |
| 2006 |
|---|
| 87 | | Oded Goldreich,
Dana Ron:
Approximating Average Parameters of Graphs.
APPROX-RANDOM 2006: 363-374 |
| 86 | | Sharon Marko,
Dana Ron:
Distance Approximation in Bounded-Degree and General Sparse Graphs.
APPROX-RANDOM 2006: 475-486 |
| 85 | | Noga Alon,
Tali Kaufman,
Michael Krivelevich,
Dana Ron:
Testing triangle-freeness in general graphs.
SODA 2006: 279-288 |
| 84 | | Michal Parnas,
Dana Ron,
Ronitt Rubinfeld:
Tolerant property testing and distance approximation.
J. Comput. Syst. Sci. 72(6): 1012-1042 (2006) |
| 83 | | Tali Kaufman,
Dana Ron:
Testing Polynomials over General Fields.
SIAM J. Comput. 36(3): 779-802 (2006) |
| 2005 |
|---|
| 82 | | Oded Goldreich,
Dana Ron:
Approximating Average Parameters of Graphs.
Sublinear Algorithms 2005 |
| 81 | | Oded Goldreich,
Dana Ron:
Approximating Average Parameters of Graphs.
Electronic Colloquium on Computational Complexity (ECCC)(073): (2005) |
| 80 | | Michal Parnas,
Dana Ron:
On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms
Electronic Colloquium on Computational Complexity (ECCC)(094): (2005) |
| 79 | | Sofya Raskhodnikova,
Dana Ron,
Ronitt Rubinfeld,
Amir Shpilka,
Adam Smith:
Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size
Electronic Colloquium on Computational Complexity (ECCC)(125): (2005) |
| 78 | | Noga Alon,
Tali Kaufman,
Michael Krivelevich,
Simon Litsyn,
Dana Ron:
Testing Reed-Muller codes.
IEEE Transactions on Information Theory 51(11): 4032-4039 (2005) |
| 77 | | Tali Kaufman,
Dana Ron:
A characterization of low-weight words that span generalized reed-muller codes.
IEEE Transactions on Information Theory 51(11): 4039-4043 (2005) |
| 2004 |
|---|
| 76 |  | Klaus Jansen,
Sanjeev Khanna,
José D. P. Rolim,
Dana Ron:
Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, and 8th International Workshop on Randomization and Computation, RANDOM 2004, Cambridge, MA, USA, August 22-24, 2004, Proceedings
Springer 2004 |
| 75 | | Tali Kaufman,
Dana Ron:
Testing Polynomials over General Fields.
FOCS 2004: 413-422 |
| 74 | | Michal Parnas,
Dana Ron,
Ronitt Rubinfeld:
Tolerant Property Testing and Distance Approximation
Electronic Colloquium on Computational Complexity (ECCC)(010): (2004) |
| 73 | | Oded Goldreich,
Dana Ron:
On Estimating the Average Degree of a Graph
Electronic Colloquium on Computational Complexity (ECCC)(013): (2004) |
| 72 | | Eldar Fischer,
Guy Kindler,
Dana Ron,
Shmuel Safra,
Alex Samorodnitsky:
Testing juntas.
J. Comput. Syst. Sci. 68(4): 753-787 (2004) |
| 71 | | Nina Mishra,
Dana Ron,
Ram Swaminathan:
A New Conceptual Clustering Framework.
Machine Learning 56(1-3): 115-151 (2004) |
| 70 | | Tali Kaufman,
Michael Krivelevich,
Dana Ron:
Tight Bounds for Testing Bipartiteness in General Graphs.
SIAM J. Comput. 33(6): 1441-1483 (2004) |
| 2003 |
|---|
| 69 | | Nina Mishra,
Dana Ron,
Ram Swaminathan:
On Finding Large Conjunctive Clusters.
COLT 2003: 448-462 |
| 68 | | Noga Alon,
Tali Kaufman,
Michael Krivelevich,
Simon Litsyn,
Dana Ron:
Testing Low-Degree Polynomials over GF(2(.
RANDOM-APPROX 2003: 188-199 |
| 67 | | Tali Kaufman,
Michael Krivelevich,
Dana Ron:
Tight Bounds for Testing Bipartiteness in General Graphs.
RANDOM-APPROX 2003: 341-353 |
| 66 | | Meir Feder,
Dana Ron,
Ami Tavory:
Bounds on Linear Codes for Network Multicast
Electronic Colloquium on Computational Complexity (ECCC) 10(033): (2003) |
| 65 | | Michal Parnas,
Dana Ron:
Testing metric properties.
Inf. Comput. 187(2): 155-195 (2003) |
| 64 | | Michal Parnas,
Dana Ron,
Ronitt Rubinfeld:
Testing membership in parenthesis languages.
Random Struct. Algorithms 22(1): 98-138 (2003) |
| 63 | | Michal Parnas,
Dana Ron,
Ronitt Rubinfeld:
On Testing Convexity and Submodularity.
SIAM J. Comput. 32(5): 1158-1184 (2003) |
| 62 | | Guy Even,
Zvi Lotker,
Dana Ron,
Shakhar Smorodinsky:
Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks.
SIAM J. Comput. 33(1): 94-136 (2003) |
| 61 | | Noga Alon,
Seannie Dar,
Michal Parnas,
Dana Ron:
Testing of Clustering.
SIAM J. Discrete Math. 16(3): 393-417 (2003) |
| 2002 |
|---|
| 60 | | Eldar Fischer,
Guy Kindler,
Dana Ron,
Shmuel Safra,
Alex Samorodnitsky:
Testing Juntas.
FOCS 2002: 103-112 |
| 59 | | Guy Even,
Zvi Lotker,
Dana Ron,
Shakhar Smorodinsky:
Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks.
FOCS 2002: 691-700 |
| 58 | | Michal Parnas,
Dana Ron,
Ronitt Rubinfeld:
On Testing Convexity and Submodularity.
RANDOM 2002: 11-25 |
| 57 | | Oded Goldreich,
Dana Ron:
Property Testing in Bounded Degree Graphs.
Algorithmica 32(2): 302-343 (2002) |
| 56 | | Michael A. Bender,
Antonio Fernández,
Dana Ron,
Amit Sahai,
Salil P. Vadhan:
The Power of a Pebble: Exploring and Mapping Directed Graphs.
Inf. Comput. 176(1): 1-21 (2002) |
| 55 | | Michal Parnas,
Dana Ron:
Testing the diameter of graphs.
Random Struct. Algorithms 20(2): 165-183 (2002) |
| 54 | | Michael A. Bender,
Dana Ron:
Testing properties of directed graphs: acyclicity and connectivity.
Random Struct. Algorithms 20(2): 184-205 (2002) |
| 53 | | Michal Parnas,
Dana Ron,
Alex Samorodnitsky:
Testing Basic Boolean Formulae.
SIAM J. Discrete Math. 16(1): 20-46 (2002) |
| 2001 |
|---|
| 52 | | Michal Parnas,
Dana Ron,
Ronitt Rubinfeld:
Testing Parenthesis Languages.
RANDOM-APPROX 2001: 261-272 |
| 51 | | Michal Parnas,
Dana Ron,
Alex Samorodnitsky:
Proclaiming Dictators and Juntas or Testing Boolean Formulae.
RANDOM-APPROX 2001: 273-284 |
| 50 | | Michal Parnas,
Dana Ron:
Testing metric properties.
STOC 2001: 276-285 |
| 49 | | Ilan Kremer,
Noam Nisan,
Dana Ron:
Errata for: "On randomized one-round communication complexity".
Computational Complexity 10(4): 314-315 (2001) |
| 48 | | Michal Parnas,
Dana Ron,
Alex Samorodnitsky:
Proclaiming Dictators and Juntas or Testing Boolean Formulae
Electronic Colloquium on Computational Complexity (ECCC) 8(063): (2001) |
| 47 | | Eric Lehman,
Dana Ron:
On Disjoint Chains of Subsets.
J. Comb. Theory, Ser. A 94(2): 399-404 (2001) |
| 2000 |
|---|
| 46 | | Noga Alon,
Seannie Dar,
Michal Parnas,
Dana Ron:
Testing of Clustering.
FOCS 2000: 240-250 |
| 45 | | Michael A. Bender,
Dana Ron:
Testing Acyclicity of Directed Graphs in Sublinear Time.
ICALP 2000: 809-820 |
| 44 | | Oded Goldreich,
Shafi Goldwasser,
Eric Lehman,
Dana Ron,
Alex Samorodnitsky:
Testing Monotonicity.
Combinatorica 20(3): 301-337 (2000) |
| 43 | | Oded Goldreich,
Dana Ron:
On Testing Expansion in Bounded-Degree Graphs
Electronic Colloquium on Computational Complexity (ECCC) 7(20): (2000) |
| 42 | | Oded Goldreich,
Dana Ron,
Madhu Sudan:
Chinese remaindering with errors.
IEEE Transactions on Information Theory 46(4): 1330-1338 (2000) |
| 41 | | Michael J. Kearns,
Dana Ron:
Testing Problems with Sublearning Sample Complexity.
J. Comput. Syst. Sci. 61(3): 428-456 (2000) |
| 1999 |
|---|
| 40 | | Michal Parnas,
Dana Ron:
Testing the Diameter of Graphs.
RANDOM-APPROX 1999: 85-96 |
| 39 | | Yevgeniy Dodis,
Oded Goldreich,
Eric Lehman,
Sofya Raskhodnikova,
Dana Ron,
Alex Samorodnitsky:
Improved Testing Algorithms for Monotonicity.
RANDOM-APPROX 1999: 97-108 |
| 38 | | Oded Goldreich,
Dana Ron,
Madhu Sudan:
Chinese Remaindering with Errors.
STOC 1999: 225-234 |
| 37 | | Oded Goldreich,
Dana Ron:
A Sublinear Bipartiteness Tester for Bounded Degree Graphs.
Combinatorica 19(3): 335-373 (1999) |
| 36 | | Ilan Kremer,
Noam Nisan,
Dana Ron:
On Randomized One-Round Communication Complexity.
Computational Complexity 8(1): 21-49 (1999) |
| 35 | | Yevgeniy Dodis,
Oded Goldreich,
Eric Lehman,
Sofya Raskhodnikova,
Dana Ron,
Alex Samorodnitsky:
Improved Testing Algorithms for Monotonicity.
Electronic Colloquium on Computational Complexity (ECCC) 6(17): (1999) |
| 34 | | Michael J. Kearns,
Dana Ron:
Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation.
Neural Computation 11(6): 1427-1453 (1999) |
| 33 | | Scott E. Decatur,
Oded Goldreich,
Dana Ron:
Computational Sample Complexity.
SIAM J. Comput. 29(3): 854-879 (1999) |
| 1998 |
|---|
| 32 | | Michael J. Kearns,
Dana Ron:
Testing Problems with Sub-Learning Sample Complexity.
COLT 1998: 268-279 |
| 31 | | Oded Goldreich,
Shafi Goldwasser,
Eric Lehman,
Dana Ron:
Testing Monotonicity.
FOCS 1998: 426-435 |
| 30 | | Michael A. Bender,
Antonio Fernández,
Dana Ron,
Amit Sahai,
Salil P. Vadhan:
The Power of a Pebble: Exploring and Mapping Directed Graphs.
STOC 1998: 269-278 |
| 29 | | Oded Goldreich,
Dana Ron:
A Sublinear Bipartiteness Tester for Bunded Degree Graphs.
STOC 1998: 289-298 |
| 28 | | Oded Goldreich,
Dana Ron,
Madhu Sudan:
Chinese Remaindering with Errors
Electronic Colloquium on Computational Complexity (ECCC) 5(62): (1998) |
| 27 | | Oded Goldreich,
Shafi Goldwasser,
Dana Ron:
Property Testing and its Connection to Learning and Approximation.
J. ACM 45(4): 653-750 (1998) |
| 26 | | Dana Ron,
Yoram Singer,
Naftali Tishby:
On the Learnability and Usage of Acyclic Probabilistic Finite Automata.
J. Comput. Syst. Sci. 56(2): 133-152 (1998) |
| 25 | | Dana Ron:
Guest Editor's Introduction.
Machine Learning 30(1): 5-6 (1998) |
| 1997 |
|---|
| 24 | | Scott E. Decatur,
Oded Goldreich,
Dana Ron:
Computational Sample Complexity.
COLT 1997: 130-142 |
| 23 | | Michael J. Kearns,
Dana Ron:
Algorithmic Stability and Sanity-Check Bounds for Leave-one-Out Cross-Validation.
COLT 1997: 152-162 |
| 22 | | Oded Goldreich,
Dana Ron:
Property Testing in Bounded Degree Graphs.
STOC 1997: 406-415 |
| 21 | | Scott E. Decatur,
Oded Goldreich,
Dana Ron:
Computational Sample Complexity
Electronic Colloquium on Computational Complexity (ECCC) 4(28): (1997) |
| 20 | | Yoav Freund,
Michael J. Kearns,
Dana Ron,
Ronitt Rubinfeld,
Robert E. Schapire,
Linda Sellie:
Efficient Learning of Typical Finite Automata from Random Walks.
Inf. Comput. 138(1): 23-48 (1997) |
| 19 | | Oded Goldreich,
Dana Ron:
On Universal Learning Algorithms.
Inf. Process. Lett. 63(3): 131-136 (1997) |
| 18 | | Dana Ron,
Ronitt Rubinfeld:
Exactly Learning Automata of Small Cover Time.
Machine Learning 27(1): 69-96 (1997) |
| 17 | | Michael J. Kearns,
Yishay Mansour,
Andrew Y. Ng,
Dana Ron:
An Experimental and Theoretical Comparison of Model Selection Methods.
Machine Learning 27(1): 7-50 (1997) |
| 1996 |
|---|
| 16 | | Oded Goldreich,
Shafi Goldwasser,
Dana Ron:
Property Testing and Its Connection to Learning and Approximation.
FOCS 1996: 339-348 |
| 15 | | Oded Goldreich,
Shafi Goldwasser,
Dana Ron:
Property Testing and its connection to Learning and Approximation
Electronic Colloquium on Computational Complexity (ECCC) 3(57): (1996) |
| 14 | | Michael Ben-Or,
Dana Ron:
Agreement in the Presence of Faults, on Networks of Bounded Degree.
Inf. Process. Lett. 57(6): 329-334 (1996) |
| 13 | | Dana Ron,
Yoram Singer,
Naftali Tishby:
The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length.
Machine Learning 25(2-3): 117-149 (1996) |
| 1995 |
|---|
| 12 | | Michael J. Kearns,
Yishay Mansour,
Andrew Y. Ng,
Dana Ron:
An Experimental and Theoretical Comparison of Model Selection Methods.
COLT 1995: 21-30 |
| 11 | | Dana Ron,
Yoram Singer,
Naftali Tishby:
On the Learnability and Usage of Acyclic Probabilistic Finite Automata.
COLT 1995: 31-40 |
| 10 | | Yoav Freund,
Dana Ron:
Learning to Model Sequences Generated by Switching Distributions.
COLT 1995: 41-50 |
| 9 | | Dana Ron,
Ronitt Rubinfeld:
Exactly Learning Automata with Small Cover Time.
COLT 1995: 427-436 |
| 8 | | Yoav Freund,
Michael J. Kearns,
Yishay Mansour,
Dana Ron,
Ronitt Rubinfeld,
Robert E. Schapire:
Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries.
FOCS 1995: 332-341 |
| 7 | | Ilan Kremer,
Noam Nisan,
Dana Ron:
On randomized one-round communication complexity.
STOC 1995: 596-605 |
| 6 | | Dana Ron,
Ronitt Rubinfeld:
Learning Fallible Deterministic Finite Automata.
Machine Learning 18(2-3): 149-185 (1995) |
| 1994 |
|---|
| 5 | | Dana Ron,
Yoram Singer,
Naftali Tishby:
Learning Probabilistic Automata with Variable Memory Length.
COLT 1994: 35-46 |
| 4 | | Michael J. Kearns,
Yishay Mansour,
Dana Ron,
Ronitt Rubinfeld,
Robert E. Schapire,
Linda Sellie:
On the learnability of discrete distributions.
STOC 1994: 273-282 |
| 1993 |
|---|
| 3 | | Dana Ron,
Ronitt Rubinfeld:
Learning Fallible Finite State Automata.
COLT 1993: 218-227 |
| 2 | | Dana Ron,
Yoram Singer,
Naftali Tishby:
The Power of Amnesia.
NIPS 1993: 176-183 |
| 1 | | Yoav Freund,
Michael J. Kearns,
Dana Ron,
Ronitt Rubinfeld,
Robert E. Schapire,
Linda Sellie:
Efficient learning of typical finite automata from random walks.
STOC 1993: 315-324 |
