Sublinear Algorithms for Approximating String Compressibility (2007)
Raskhodnikova, Sofya, Ron, Dana, Rubinfeld, Ronitt, Smith, Adam
We raise the question of approximating the compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless...
Testing the Diameter of Graphs (2004)
We propose a general model for testing graph properties, which extends and simpli es the bounded degree model of [GR97]. In this model we present a family of algorithms that test whether the diameter...
Testing Properties of Directed Graphs: Acyclicity and Connectivity Michael A. Bender (2004)
This paper initiates the study of testing properties of directed graphs. In particular, the paper considers the most basic property of directed graphs { acyclicity. Because the choice of...
The Power of a Pebble: Exploring and Mapping Directed Graphs (2004)
Michael A. Bender, Juan Carlos, Dana Ron, Amit Sahai, Salil Vadhan
Exploring and mapping an unknown environment is a fundamental problem that is studied in a variety of contexts. Many works have focused on finding efficient solutions to restricted versions of the...
On Estimating the Average Degree of a Graph (2004)
Following Feige, we consider the problem of estimating the average degree of a graph. Using eighbor queries" as well as degree queries", we show that the average degree can be approximated...
Tight Bounds for Testing Bipartiteness in General Graphs (2004)
Tali Kaufman, Michael Krivelevich, Dana Ron
In this paper we consider the problem of testing bipartiteness of general graphs. The problem has previously been studied in two models, one most suitable for dense graphs, and one most suitable for...
Centralized deterministic broadcasting in undirected multi-hop radio networks (2004)
Kowalski, Dariusz, Pelc, Andrzej, Jansen, Klaus, Khanna, Sanjeev, Rolim, José, Ron, Dana
On Finding Large Conjunctive Clusters (2003)
Nina Mishra, Dana Ron, Ram Swaminathan
We propose a new formulation of the clustering problem that diers from previous work in several aspects. First, the goal is to explicitly output a collection of simple and meaningful conjunctive...
Bounds on Linear Codes for Network Multicast (2003)
Ami Tavory, Meir Feder, Dana Ron
Traditionally, communication networks are composed of routing nodes, which relay and duplicate data. Work in recent years has shown that for the case of multicast, an improvement in both rate and...
Property Testing in Bounded Degree Graphs (2003)
We further develop the study of testing graph properties as initiated by Goldreich, Goldwasser and Ron. Loosely speaking, given an oracle access to a graph, we wish to distinguish the case the graph...
Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
We show that a boolean valued function over n variables, where each variable ranges in an arbitrary probability space, can be tested for the property of depending on only J of them using a number of...
A Markovian Lattice Model (2003)
Leonid Kontorovich, Dana Ron, Yoram Singer
We describe a new formalism for word morphology. Our model views word generation as a random walk on a lattice of units where each unit is a set of (short) strings. The model naturally incorporates...
Leonid Kontorovich, Dana Ron, Yoram Singer
We describe a new formalism for word morphology. Our model views word generation as a random walk on a trellis of units where each unit is a set of (short) strings. The model naturally incorporates...
We describe a new boosting algorithm that is the first such algorithm to be both smooth and adaptive. These two features make possible performance improvements for many learning tasks whose solutions...
Testing Basic Boolean Formulae (2003)
Michal Parnas, Dana Ron, Alex Samorodnitsky
We consider the problem of determining whether a given function f : f0; 1g belongs to a certain class of Boolean functions F or whether it is far from the class. More precisely, given query access to...
Testing Properties of Directed Graphs: Acyclicity and Connectivity (2003)
This paper initiates the study of testing properties of directed graphs. In particular, the paper considers the most basic property of directed graphs { acyclicity. Because the choice of...
Guy Even, Zvi Lotker, Dana Ron, Shakhar Smorodinsky
Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem that we call Minimum Conflict-Free Coloring (Min-CF-Coloring). In its general form, the...
On Testing Convexity and Submodularity (2003)
Michal Parnas, Dana Ron, Ronitt Rubinfeld
Convex and Submodular functions play an important role in many applications, and in particular in combinatorial optimization. Here we study two special cases: convexity in one dimension and...
Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
We show that a Boolean function over n Boolean variables can be tested for the property of depending on only k of them, using a number of queries that depends only on k and the approximation...
On Online Learning of Decision Lists (2002)
Ziv Nevo, Ran El-yaniv, Dana Ron
A fundamental open problem in computational learning theory is whether there is an attribute efficient learning algorithm for the concept class of decision lists (Rivest, 1987; Blum, 1996). We...
Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
We show that a boolean function over n variables can be tested for the property of depending on only k of them, using a number of queries that depends only on k and the approximation parameter #. We...
Machine Learning, 27, 7--50 (1997) c (2002)
Michael Kearns, Dana Ron, M. Long
We investigate the problem of model selection in the setting of supervised learning of boolean functions from independent random examples. More precisely, we compare methods for finding a balance...
Guy Even, Zvi Lotker, Dana Ron, Shakhar Smorodinsky
Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem that we call Minimum Conict-Free Coloring (Min-CF-Coloring). In its general form, the...
Nader H. Bshouty, Nadav Eiron, Dana Ron
We present results concerning the learning of Monotone DNF (MDNF) from Incomplete Membership Queries and Equivalence Queries. Our main result is a new algorithm that allows e#cient learning of MDNF...
Improved Testing Algorithms for Monotonicity (2002)
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
We present improved algorithms for testing monotonicity of functions. Namely, given the ability to query an unknown function f : Sigma 7! Xi, where Sigma and Xi are finite ordered sets, the test...
Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, Alex Samorodnitsky
We present a (randomized) test for monotonicity of Boolean functions. Namely, given the ability to query an unknown function f : f0; 1g 7! f0; 1g at arguments of its choice, the test always accepts a...
Improved Testing Algorithms for Monotonicity (2002)
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
We present improved algorithms for testing monotonicity of functions. Namely, given the ability to query an unknown function f : Sigma 7! Xi, where Sigma and Xi are finite ordered sets, the test...
Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, Alex Samorodnitsky
We present a (randomized) test for monotonicity of Boolean functions. Namely, given the ability to query an unknown function f : f0; 1g 7! f0; 1g at arguments of its choice, the test always accepts a...
A Sublinear Bipartiteness Tester for Bounded Degree Graphs (2002)
A Sublinear, Bipartiteness Tester, Oded Goldreich, Dana Ron
We present a sublinear-time algorithm for testing whether a bounded degree graph is bipartite or far from being bipartite. Graphs are represented by incidence lists of bounded length d, and the...
Conflict-Free Colorings of Unit Disks (2002)
Guy Even, Zvi Lotker, Dana Ron
Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem that we call Minimum Conflict-Free Coloring (Min-CF-Coloring). In its general form, the...
We de ne notions of stability for learning algorithms and show how to use these notions to derive generalization error bounds based on the empirical error and the leave-one-out error. The methods we...
On Using Extended Statistical Queries to Avoid Membership Queries (2002)
Nader H. Bshouty, Vitaly Feldman, Dana Ron
The Kushilevitz-Mansour (KM) algorithm is an algorithm that finds all the "large" Fourier coe#cients of a Boolean function. It is the main tool for learning decision trees and DNF expressions in the...
We investigate two dierent notions of size" which appear naturally in Statistical Learning Theory. We present quantitative estimates on the fat-shattering dimension and on the covering numbers of...
Testing Parenthesis Languages (2001)
Michal Parnas, Dana Ron, Ronitt Rubinfeld
We continue the investigation of properties dened by formal languages. This study was initiated by Alon et. al. [AKNS99] who described an algorithm for testing properties dened by regular languages....
Testing Parenthesis Languages (2001)
Michal Parnas, Dana Ron, Ronitt Rubinfeld
We continue the investigation of properties dened by formal languages. This study was initiated by Alon et. al. [AKNS99] who described an algorithm for testing properties dened by regular languages....
Proclaiming Dictators and Juntas or Testing Boolean Formulae (2001)
Michal Parnas, Dana Ron, Alex Samorodnitsky
We consider the problem of determining whether a given function f : f0; 1g n ! f0; 1g belongs to a certain class of Boolean functions F or whether it is far from the class. More precisely, given...
Chinese Remaindering with Errors (2001)
The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder modulo k relatively prime integers p 1 ; : : : ; p k , provided m ! Q k i=1 p i . Thus the...
Chinese Remaindering with Errors (2001)
Oded Goldreich, Dana Ron, Madhu Sudan
The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder modulo k relatively prime integers p1 ; : : : ; pk , provided m ! Q k i=1 p i . Thus the residues...
Testing Metric Properties (2001)
Finite metric spaces, and in particular tree metrics play an important role in various disciplines
Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire
this paper, games are played by two players. One will be called the adversary and the other the strategy learning algorithm. We think of the adversary as a fixed resource-bounded computational...
An Experimental and Theoretical Comparison (2001)
Michael Kearns, Yishay Mansour, Andrew Y. Ng, Dana Ron
this paper is to provide such a comparison, and more importantly, to describe the general conclusions to which it has led. Relying on evidence that is divided between controlled experimental results...
Testing Problems with Sub-Learning Sample Complexity (2001)
We study the problem of determining, for a class of functions H, whether an unknown target function f is contained in H or is "far" from any function in H. Thus, in contrast to problems of learning,...
Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
this paper, we concentrate on discrete
Algorithmic Stability and Sanity-Check Bounds (2001)
In this paper we prove sanity-check bounds for the error of the leave-one-out crossvalidation estimate of the generalization error: that is, bounds showing that the worst-case error of this estimate...
On Testing Expansion in Bounded-Degree Graphs (2000)
We consider testing graph expansion in the bounded-degree graph model (as formulated in [1]). Specifically, we refer to algorithms for testing whether the graph has a second eigenvalue bounded above...
this technical aspect (as in the bounded-degree model the closest graph having the property must have at most dN edges and degree bound d as well)
Learning Fallible Deterministic Finite Automata (2000)
this paper, and the authors solve it only under the assumption that the learner is either given a distinguishing sequence or can generate one efficiently with high probability. It is known (and there...
Exactly Learning Automata with Small Cover Time (2000)
We present algorithms for exactly learning unknown environments that can be described by deterministic finite automata. The learner performs a walk on the target automaton, where at each step it...
Testing Acyclicity of Directed Graphs in Sublinear Time (2000)
This paper initiates the study of testing properties of directed graphs. In particular, the paper considers the most basic property of directed graphs -- acyclicity. Because the choice of...
Chinese Remaindering with Errors (2000)
The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder modulo k relatively prime integers p 1 ; : : : ; p k , provided m ! Q k i=1 p i . Thus the...
The Power of a Pebble: Exploring and Mapping Directed Graphs (2000)
Michael A. Bender, Juan Carlos, Dana Ron, Amit Sahai, Salil Vadhan
Exploring and mapping an unknown environment is a fundamental problem that is studied in a variety of contexts. Many results have focused on finding efficient solutions to restricted versions of the...
Noga Alon, Seannie Dar, Michal Parnas, Dana Ron
A set X of points in ! d is (k; b)-clusterable if X can be partitioned into k subsets (clusters) so that the diameter (alternatively, the radius) of each cluster is at most b. We present algorithms...
this technical aspect (as in the bounded-degree model the closest graph having the property must have at most dN edges and degree bound d as well).
Michael A. Bender, Antonio Fernandez, Dana Ron, Amit Sahai, Salil Vadhan
Exploring and mapping an unknown environment is a fundamental problem, which is studied in various contexts. Many works have focused on finding efficient solutions to restricted versions of the...
Michael A. Bender, Juan Carlos, Dana Ron, Amit Sahai, Salil Vadhan
Exploring and mapping an unknown environment is a fundamental problem that is studied in a variety of contexts. Many results have focused on nding ecient solutions to restricted versions of the...
Improved Testing Algorithms for Monotonicity (2000)
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
We present improved algorithms for testing monotonicity of functions. Namely, given the ability to query an unknown function f : Sigma n 7! Xi, where Sigma and Xi are finite ordered sets, the test...
Testing Acyclicity of Directed Graphs in Sublinear Time (2000)
This paper initiates the study of testing properties of directed graphs. In particular, the paper considers the most basic property of directed graphs -- acyclicity. Because the choice of...
Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, Alex Samorodnitsky
We present a (randomized) test for monotonicity of Boolean functions. Namely, given the ability to query an unknown function f : f0; 1g n ! f0; 1g at arguments of its choice, the test always accepts...
Chinese Remaindering with Errors (2000)
Oded Goldreich, Dana Ron, Madhu Sudan
The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder modulo k relatively prime integers p 1 ; : : : ; p k , provided m ! i=1 p i . Thus the residues...
The Power of a Pebble: Exploring and Mapping Directed Graphs (1999)
Michael A. Bender, Dana Ron, Amit Sahai, Salil Vadhan
Exploring and mapping an unknown environment is a fundamental problem that is studied in a variety of contexts. Many works have focused on finding efficient solutions to restricted versions of the...
An Experimental and Theoretical Comparison of Model Selection Methods (1999)
Michael Kearns, Yishay Mansour, Andrew Y. Ng, Dana Ron
this paper is to provide such a comparison, and more importantly, to describe the general conclusions to which it has led. Relying on evidence that is divided between controlled experimental results...
On the Learnability of Discrete Distributions (1999)
Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
this paper, we concentrate on discrete distributions over f0; 1g
Exactly Learning Automata with Small Cover Time (1999)
We present algorithms for exactly learning unknown environments that can be described by deterministic finite automata. The learner performs a walk on the target automaton, where at each step it...
Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire
this paper, games are played by two players. One will be called the adversary and the other the strategy learning algorithm. We think of the adversary as a fixed resource-bounded computational...
Efficient Learning of Typical Finite Automata from Random Walks (1999)
Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
This paper describes new and efficient algorithms for learning deterministic finite automata. Our approach is primarily distinguished by two features: (1) the adoption of an average-case setting to...
Learning Fallible Deterministic Finite Automata (1999)
this paper, and the authors solve it only under the assumption that the learner is either given a distinguishing sequence or can generate one efficiently with high probability. It is known (and there...
Testing the Diameter of Graphs (1999)
We propose a general model for testing graph properties, which extends and simplifies the bounded degree model of [GR97]. In this model we present a family of algorithms that test whether the...
Improved Testing Algorithms for Monotonicity (1999)
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
We present improved algorithms for testing monotonicity of functions. Namely, given the ability to query an unknown function f : Sigma n 7! Xi, where Sigma and Xi are finite ordered sets, the test...
Property Testing and its Connection to Learning and Approximation (1999)
Oded Goldreich, Shafi Goldwasser, Dana Ron
We study the question of determining whether an unknown function has a particular property or is ffl-far from any function with that property. A property testing algorithm is given a sample of the...
Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire
this paper, games are played by two players. One will be called the adversary and the other the strategy learning algorithm. We think of the adversary as a fixed resource-bounded computational...
On the Learnability of Discrete Distributions (Extended Abstract) (1999)
Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
this paper, we concentrate on discrete distributions over f0; 1g
Property Testing in Bounded Degree Graphs (1999)
We further develop the study of testing graph properties as initiated by Goldreich, Goldwasser and Ron. Whereas they view graphs as represented by their adjacency matrix and measure distance between...
On the Learnability and Usage of Acyclic Probabilistic Finite Automata (1999)
Dana Ron, Yoram Singer, Naftali Tishby
We propose and analyze a distribution learning algorithm for a subclass of Acyclic Probabilistic Finite Automata (APFA). This subclass is characterized by a certain distinguishability property of the...
Property Testing in Bounded Degree Graphs (1999)
We further develop the study of testing graph properties as initiated by Goldreich, Goldwasser and Ron. Whereas they view graphs as represented by their adjacency matrix and measure distance between...
Property Testing and its Connection to Learning and Approximation (1999)
Oded Goldreich, Shafi Goldwasser, Dana Ron
In this paper, we consider the question of determining whether a function f has property P or is ffl-far from any function with property P. A property testing algorithm is given a sample of the value...
Testing Problems with Sub-Learning Sample Complexity (1999)
We study the problem of determining, for a class of functions H , whether an unknown target function f is contained in H or is "far" from any function in H . Thus, in contrast to problems of...
An Experimental and Theoretical Comparison of Model Selection Methods (1999)
Michael Kearns, Yishay Mansour, Andrew Y. Ng, Dana Ron
We investigate the problem of model selection in the setting of supervised learning of boolean functions from independent random examples. More precisely, we compare methods for finding a balance...
On the Learnability of Discrete Distributions (1999)
Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
this paper, we concentrate on discrete distributions over f0; 1g