Finding a Dense-Core in Jellyfish graphs (2009)
Mira Gonen, Dana Ron, Udi Weinsberg, Avishai Wool
The connectivity of the Internet crucially depends on the relationships between thousands of Autonomous Systems (ASes) that exchange routing information using the Border Gateway Protocol (BGP). These...
Property Testing: A Learning Theory Perspective (2009)
Property testing deals with tasks where the goal is to distinguish between the case that an object (e.g., function or graph) has a prespecified property (e.g., the function is linear or the graph is...
Testing Reed Muller Codes ∗ (2009)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
A code is locally testable if there is a way to indicate with high probability that a vector is far enough from any codeword by accessing only a very small number of the vector’s bits. We show that...
We consider the question of whether adaptivity can improve the complexity of property testing algorithms in the dense graphs model. Goldreich and Trevisan (Random Structures and Algorithms, 2003)...
On Proximity Oblivious Testing (2009)
We initiate a systematic study of a special type of property testers. These testers consist of repeating a basic test for a number of times that depends on the proximity parameter, whereas the basic...
Testing low-degree polynomials over GF(2) (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
Abstract. We describe an efficient randomized algorithm to test if a given binary function � � ����� � � ���� � is a low-degree polynomial (that is, a sum of low-degree...
Testing low-degree polynomials over GF(2), booktitle (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
We describe an efficient randomized algorithm to test if a given binary function f: {0, 1} n → {0, 1} is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k ≥...
Abstract Testing Triangle-Freeness in General Graphs (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron
In this paper we consider the problem of testing whether a graph is triangle-free, and more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are...
We consider the problem of estimating the size, V C(G), of a minimum vertex cover of a graph G, in sublinear time, by querying the incidence relation of the graph. We say that an algorithm is an (α,...
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...
For a given graph G over n vertices, let OPT G denote the size of an optimal solution in G of a particular minimization problem (e.g., the size of a minimum vertex cover). A randomized algorithm will...
Abotract The Power of a Pebble: Exploring and Mapping Directed Graphs (2008)
Michael A. Bender, Antonio Fernfindezt, Dana Ron, Amit Salil Vadhana
Exploring and mapping an unknown environment is a fun-damcntal problem that is studied in a variety of contexts. Many works have focused on finding efficient solutions to re-atrictcd versions of the...
We consider the question of whether adaptivity can improve the complexity of property testing algorithms in the dense graphs model. It is known that there can be at most a quadratic gap between...
In this paper we study the problem of approximating the distance of a function to convexity. Namely, we are interested in randomized sublinear algorithms that approximate the Hamming distance between...
Ron Begleiter, Ran El-yaniv, Dana Ron
We present worst case bounds for the learning rate of a known prediction method that is based on hierarchical applications of binary context tree weighting (CTW) predictors. A heuristic application...
Ido Ben-eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron
the strength of query types in property testing:
Algorithmic aspects of property testing in the dense graphs model. ECCC (2008)
In this paper we consider two basic questions regarding the query complexity of testing graph properties in the adjacency matrix model. The first question refers to the relation between adaptive and...
A Note on Testing Monotonicity (2007)
Oded Goldreich, Shafi Goldwasser, Dana Ron
We show that under a certain conjecture regarding the boolean lattice, there exists an efficient algorithm for testing whether a function is monotone or ffl-far from monotone. Note: The said...
On Universal Learning Algorithms (2007)
We observe that there exists a universal learning algorithm which PAC-learns every concept class within complexity which is linearly related to the complexity of the best learning algorithm for this...
On Universal Learning Algorithms (2007)
We observe that there exists a universal learning algorithm that pac-learns every concept class within complexity that is linearly related to the complexity of the best learning algorithm for this...
A Markovian Lattice Model for the Acquisition of Morphological Structure (2007)
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...
A Markov Model for the Acquisition of Morphological Structure (2007)
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...
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 Con ict-Free Coloring (Min-CF-Coloring). In its general form, the...
Eldar Fischer, Guy Kindler, Dana Ron, 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...
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 7! f0; 1g at arguments of its choice, the test always accepts...
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...
for Bounded Degree Graphs (2007)
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...
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 Con ict-Free Coloring (Min-CF-Coloring). In its general form, the...
Michael A. Bender, Antonio Fernandez, Dana Ron, Amit Sahai, Salil Vadhan
Abstract. 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...
Deterministic Finite Automata (2007)
Suppose a scientist is given a comprehensive set of data that has been collected, and is asked to come up with a simple explanation of it. Such situations might include trying to explain data...
Exactly Learning Automata with Small Cover Time (2007)
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...
A Probabilistic Error-Correcting Scheme (2007)
Scott Decatur, Oded Goldreich, Dana Ron
In the course of research in Computational Learning Theory, we found ourselves in need of an error-correcting encoding scheme for which few bits in the codeword yield no information about the plain...
A Probabilistic Error-Correcting Scheme (2007)
Scott Decatur, Oded Goldreich, Dana Ron
In the course of research in Computational Learning Theory, we found ourselves in need of an error-correcting encoding scheme for which few bits in the codeword yield no information about the plain...
Nina Mishra, Dana Ron, Ram Swaminathan
Abstract. 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...
On Estimating the Average Degree of a Graph (2007)
Oded Goldreich, Rehovot Israel, Dana Ron
Following Feige, we consider the problem of estimating the average degree of a graph. Using \neighbor queries" as well as \degree queries", we show that the average degree can be...
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...
A.: Finding a dense-core in jellyfish graphs (2007)
Mira Gonen, Dana Ron, Udi Weinsberg, Avishai Wool
Abstract. The connectivity of the Internet crucially depends on the relationships between thousands of Autonomous Systems (ASes) that exchange routing information using the Border Gateway Protocol...
1.1 An Almost Linear Lower Bound for Approximation with an Additive Error..... 2 (2007)
Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam Smith
We consider the problem of approximating the support size of a distribution from a small number of samples, when each element in the distribution appears with probability at least 1 n. This problem...
Scheduling with Conflicts: Online and Offline Algorithms (2007)
Guy Even, Magnús M. Halldórsson, Lotem Kaplan, Dana Ron
We consider the following problem of scheduling with conflicts (SWC): Find a minimum makespan schedule on identical machines where conflicting jobs cannot be scheduled concurrently. We study the...
Inspired by Feige (36th STOC, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph...
Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam Smith
We consider the problem of approximating the support size of a distribution from a small number of samples, when each element in the distribution appears with probability at least 1 n. This problem...
Scheduling with Conflicts: Online and Offline Algorithms (2007)
Guy Even, Magnús M. Halldórsson, Lotem Kaplan, Dana Ron
We consider the following problem of scheduling with conflicts (SWC): Find a minimum makespan schedule on identical machines where conflicting jobs cannot be scheduled concurrently. We study the...
Sublinear algorithms for approximating string compressibility (2007)
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith
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...
Approximating the distance to monotonicity in high dimensions. Available from (2007)
In this paper we study the problem of approximating the distance of a function over [n] d to monotonicity. Namely, we are interested in randomized sublinear algorithms that approximate the Hamming...
Michael Schmitt, Laura Martignon, Dana Ron
Fast and frugal heuristics are well studied models of bounded rationality. Psychological research has proposed the take-the-best heuristic as a successful strategy in decision making with limited...
Toward Attribute Efficient Learning of Decision Lists and Parities (2006)
Adam R. Klivans, Rocco A. Servedio, Dana Ron
We consider two well-studied problems regarding attribute efficient learning: learning decision lists and learning parity functions. First, we give an algorithm for learning decision lists of length...
Testing triangle-freeness in general graphs (2006)
Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron
In this paper we consider the problem of testing whether a graph is triangle-free, and more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are...
Testing triangle-freeness in general graphs (2006)
Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron
In this paper we consider the problem of testing whether a graph is triangle-free, and more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are...
Distance approximation in bounded-degree and general sparse graphs (2006)
We address the problem of approximating the distance of bounded degree and general sparse graphs from having some predetermined graph property P. Namely, we are interested in sublinear algorithms for...
Approximating Average Parameters of Graphs (2006)
Inspired by Feige (36th STOC, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph...
Centralized deterministic broadcasting in undirected multi-hop radio networks (2004)
Kowalski, Dariusz, Pelc, Andrzej, Jansen, Klaus, Khanna, Sanjeev, Rolim, José, Ron, Dana
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...
PAC-learnability of Probabilistic Deterministic Finite State Automata (2004)
Alexander Clark, Franck Thollard, Rue Docteur, Paul Michelon, ...
We study the learnability of Probabilistic Deterministic Finite State Automata under a modified PAC-learning criterion. We argue that it is necessary to add additional parameters to the sample...
Testing Reed Muller Codes \Lambda (2004)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
Abstract A code is locally testable if there is a way to indicate with high probability that a vector is far enough from any codeword by accessing only a very small number of the vector's bits....
The dynamics of adaboost: Cyclic behavior and convergence of margins (2004)
Cynthia Rudin, Ingrid Daubechies, Robert E. Schapire, Dana Ron
In order to study the convergence properties of the AdaBoost algorithm, we reduce AdaBoost to a nonlinear iterated map and study the evolution of its weight vectors. This dynamical systems approach...
Centralized deterministic broadcasting in undirected multi-hop radio networks (2004)
Kowalski, Dariusz, Pelc, Andrzej, Jansen, Klaus, Khanna, Sanjeev, Rolim, José, Ron, Dana
A New Conceptual Clustering Framework (2004)
Nina Mishra, Dana Ron, Ram Swaminathan
We propose a new formulation of the conceptual clustering problem where the goal is to explicitly output a collection of simple and meaningful conjunctions of attributes that define the clusters. The...
On Online Learning of Decision Lists (2003)
A fundamental open problem in computational learning theory is whether there is an attribute e#cient learning algorithm for the concept class of decision lists (Rivest, 1987; Blum, 1996). We consider...
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...
On the Proper Learning of Axis-Parallel Concepts (2003)
Nader H. Bshouty, Lynn Burroughs, Dana Ron
We study the proper learnability of axis-parallel concept classes in the PAC-learning and exactlearning models. These classes include union of boxes, DNF, decision trees and multivariate polynomials....
On the Proper Learning of Axis-Parallel Concepts (2003)
Nader H. Bshouty, Lynn Burroughs, Dana Ron
We study the proper learnability of axis-parallel concept classes in the PAC-learning and exactlearning models. These classes include union of boxes, DNF, decision trees and multivariate polynomials....
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...
Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning (2003)
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...
Ziv Nevo, Ran El-yaniv, Dana Ron
A fundamental open problem in computational learning theory is whether there is an attribute e#cient learning algorithm for the concept class of decision lists (Rivest, 1987; Blum, 1996). We consider...
On Online Learning of Decision Lists (2003)
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...
A Markov Model for the Acquisition of Morphological Structure (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 trellis of units where each unit is a set of (short) strings. The model naturally incorporates...
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...
No unbiased estimator of the variance of K-fold cross-validation (2003)
Yoshua Bengio, Yves Grandvalet, Dana Ron
Most machine learning researchers perform quantitative experiments to estimate generalization error and compare the performance of different algorithms (in particular, their proposed algorithm). In...
Tight Bounds for Testing Bipartiteness in General Graphs (2003)
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...
On the Proper Learning of Axis-Parallel Concepts (2003)
Nader H. Bshouty, Lynn Burroughs, Dana Ron
We study the proper learnability of axis-parallel concept classes in the PAC-learning and exactlearning models. These classes include union of boxes, DNF, decision trees and multivariate polynomials....
On finding large conjunctive clusters (2003)
Nina Mishra, Dana Ron, Ram Swaminathan
Abstract. We propose a new formulation of the clustering problem that differs from previous work in several aspects. First, the goal is to explicitly output a collection of simple and meaningful...
Testing Low-Degree Polynomials over GF(2) (2003)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
We describe an efficient randomized algorithm to test if a given binary function f : f0; 1g ! f0; 1g is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k 1 and a...
Testing Low-Degree Polynomials over GF(2) (2003)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
We describe an efficient randomized algorithm to test if a given binary function f : f0; 1g ! f0; 1g is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k 1 and a...
Optimally-smooth adaptive boosting and application to agnostic learning (2003)
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 (2002)
Michal Parnas, Dana Ron, Alex Samorodnitsky
We consider the problem of determining whether a given function f: f0; 1g
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...
On using extended statistical queries to avoid membership queries (2002)
Nader H. Bshouty, Vitaly Feldman, Dana Ron, Nader H. Bshouty, Vitaly Feldman
The Kushilevitz-Mansour (KM) algorithm is an algorithm that finds all the “large” Fourier coefficients of a Boolean function. It is the main tool for learning decision trees and DNF expressions...
On using extended statistical queries to avoid membership queries (2002)
Nader H. Bshouty, Vitaly Feldman, Dana Ron, Nader H. Bshouty, Vitaly Feldman
The Kushilevitz-Mansour (KM) algorithm is an algorithm that finds all the “large” Fourier coefficients of a Boolean function. It is the main tool for learning decision trees and DNF expressions...
Eldar Fischer Guy, Guy Kindler, Dana Ron, 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...
Palaiseau France Andr, Olivier Bousquet, Dana Ron
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...
Testing Properties of Directed Graphs: Acyclicity and Connectivity (2002)
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...
Learning monotone dnf from a teacher that almost does not answer membership queries (2002)
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 efficient learning of MDNF...
Stability and generalization (2002)
Olivier Bousquet, André Elisseeff, Dana Ron
We define 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...
Eldar Fischer Guy, 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...
Learning Monotone DNF from a Teacher that Almost Does Not Answer Membership Queries (2002)
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...
On using extended statistical queries to avoid membership queries (2002)
Dana Ron, Nader H. Bshouty, Nader H. Bshouty, Vitaly Feldman, Vitaly Feldman
The Kushilevitz-Mansour (KM) algorithm is an algorithm that finds all the “large” Fourier coefficients of a Boolean function. It is the main tool for learning decision trees and DNF expressions...
On the size of convex hulls of small sets (2001)
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...
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 metric properties (2001)
Finite metric spaces, and in particular tree metrics play an important role in various disciplines such as evolutionary biology and statistics. A natural family of problems concerning metrics is...
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
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....
Michal Parnas, Dana Ron, Alex Samorodnitsky
We consider the problem of determining whether a given function ¢ £ ¤¥¦§¨ © � ¤¥¦§ ¨ belongs to a certain class of Boolean functions � or whether it is far from the class. More...
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...
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...
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).
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...
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...
Computational sample complexity (1999)
Scott E. Decatur, Oded Goldreich, Dana Ron
In a variety of PAC learning models, a tradeoff between time and information seems to exist: with unlimited time, a small amount of information suffices, but with time restrictions, more information...
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...
Chinese remaindering with errors (1999)
z 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 residues...
On randomized one-round communication complexity (1999)
Ilan Kremer, Noam Nisan, Dana Ron
Abstract. We present several results regarding randomized one-round communication complexity. Our results include a connection to the VCdimension, a study of the problem of computing the inner...
Chinese remaindering with errors (1999)
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 residues...
Chinese remaindering with errors (1999)
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 of...
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...
Abstract 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,...
Algorithmic stability and sanity-check bounds for leave-one-out cross-validation (1999)
Abstract: 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...
Algorithmic stability and sanity-check bounds for leave-one-out cross-validation (1999)
Abstract: In this paper we prove sanity-check bounds for the error of the leave-one-out cross-validation estimate of the generalization error: that is, bounds showing that the worst-case error of...
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: Σ n ↦ → Ξ, where Σ and Ξ are finite ordered sets, the test...
Testing problems with sub-learning sample complexity (1998)
We study the problem of determining, for a class of functions ¡ , whether an unknown target function ¢ is contained in ¡ or is “far ” from any function in ¡. Thus, in contrast to problems of...
The Power of a Pebble: Exploring and Mapping Directed Graphs (1998)
Michael Bender, Antonio Fernandez, Dana Ron, Amit Sahai, Salil Vadhan
. Exploring and mapping an unknown environment is a fundamental problem, which is studied in a variety of contexts. Many works have focused on finding efficient solutions to restricted versions of...
The Power of a Pebble: Exploring and Mapping Directed Graphs (1998)
Michael A. Bender, Antonio Fernández, 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...
Chinese Remaindering with Errors (1998)
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 ! Q k i=1 p i . Thus the...
Testing Problems with Sub-Learning Sample Complexity (1998)
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...
Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron
We present a (randomized) test for monotonicity of Boolean functions. Namely, given the ability to query an unknown function f : f0; 1g n 7! f0; 1g at arguments of its choice, the test always accepts...
Property Testing and its Connection to Learning and Approximation (1998)
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...
A Sublinear Bipartiteness Tester for Bounded Degree Graphs (1998)
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...
Property Testing in Bounded Degree Graphs (1998)
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...
Chinese Remaindering with Errors (1998)
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 ! Q k i=1 p i . Thus the...
The Power of a Pebble: Exploring and Mapping Directed Graphs (1998)
Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, Salil Vadhan
. Exploring and mapping an unknown environment is a fundamental problem, which is studied in a variety of contexts. Many works have focused on finding efficient solutions to restricted versions of...
On restricted-focus-of-attention learnability of Boolean functions (1998)
Andreas Birkendorf, Eli Dichterman, ...
Abstract. In the k-Restricted-Focus-of-Attention (k-RFA) model, only k of the n attributes of each example are revealed to the learner, although the set of visible attributes in each example is...
Testing problems with sub-learning sample complexity (1998)
We study the problem of determining, for a class of functions ¡, whether an unknown target function is contained in ¡ or is “far ” from any function in ¡. Thus, in contrast to problems of...
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...
Testing problems with sub-learning sample complexity (1998)
We study the problem of determining, for a class of functionsH, whether an unknown target functionf is contained inHor is “far ” from any function inH. Thus, in contrast to problems of learning,...
The Power of a Pebble: Exploring and Mapping Directed Graphs (1998)
Michael A. Bender, Antonio Fernández, 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...
Michael A. Bender, Antonio Fernández, 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...
Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron
We present a (randomized) test for monotonicity of Boolean functions. Namely, given the ability to query an unknown £¥¤§¦©¨������������¦©¨������ function...
Computational Sample Complexity (1997)
Scott Decatur, Oded Goldreich, Dana Ron
In a variety of PAC learning models, a tradeoff between time and information seems to exist: with unlimited time, a small amount of information suffices, but with time restrictions, more information...
Property Testing in Bounded Degree Graphs (1997)
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 in Bounded Degree Graphs (1997)
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...
Model-Based Learning of Interaction Strategies in Multi-Agent Systems (1997)
David Carmel, In Milind Tambe, Piotr Gmytrasiewicz, B. Trakhtenbrot, Y. Barzdin, ...
ordinate actions in multi-agent systems. In Proceeding of the International Joint Conference on Artificial Intelligence (IJCAI 93), pages 311--316, August 1993. [106] G. Weiß and S. Sen. Adaptation...
Exactly Learning Automata of Small Cover Time (1997)
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...
Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation (1997)
In this paper we prove sanity-check bounds for the error of the leave-one-out cross-validation estimate of the generalization error: that is, bounds showing that the worst-case error of this estimate...
Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation (1997)
: 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...
Property Testing in Bounded Degree Graphs (1997)
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...
An Experimental and Theoretical Comparison of Model Selection Methods (1997)
Michael Kearns, Yishay Mansour, Andrew Ng, 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...
The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length (1996)
Dana Ron, Yoram Singer, NAFTALI TISHBY
. We propose and analyze a distribution learning algorithm for variable memory length Markov processes. These processes can be described by a subclass of probabilistic finite automata which we name...
The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length (1996)
. We propose and analyze a distribution learning algorithm for variable memory length Markov processes. These processes can be described by a subclass of probabilistic finite automata which we name...
Yoav Freund Att, Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, 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...
Yoav Freund Att, Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, ...
We study the problem of efficiently learning to play a game optimally against an unknown adversary chosen from a computationally bounded class. We both contribute to the line of research on playing...
Agreement In the Presence of Faults, On Networks of Bounded Degree (1996)
We present networks of bounded degree and a fully polynomial almost everywhere agreement scheme which tolerate, with high probability, randomly located faulty processors, where processors fail...
The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length (1996)
Dana Ron, Yoram Singer, Naftali Tishby
We propose and analyze a distribution learning algorithm for variable memory length Markov processes. These processes can be described by a subclass of probabilistic finite automata which we name...
The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length (1996)
. We propose and analyze a distribution learning algorithm for variable memory length Markov processes. These processes can be described by a subclass of probabilistic finite automata which we name...
Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, 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...
Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire
We study the problem of efficiently learning to play a game optimally against an unknown adversary chosen from a computationally bounded class. We both contribute to the line of research on playing...
Yoav Freund, Ronitt Rubinfeld, Michael Kearns, Robert E. Schapire, Dana Ron, Linda Sellie
This paper describes new and e cient algorithms for learning deterministic nite automata. Our approach is primarily distinguished by two features: (1) the adoption of an average-case setting to model...
On the Learnability and Usage of Acyclic Probabilistic Finite Automata (1995)
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...
On Randomized One-Round Communication Complexity (1995)
Ilan Kremer, Noam Nisan, Dana Ron
We present several results regarding randomized one-round communication complexity. These include a connection to the VC dimension, a study of the problem of computing the inner product of two real...
On the Learnability and Usage of Acyclic Probabilistic Finite Automata (1995)
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...
On Randomized One-Round Communication Complexity (1995)
Ilan Kremer, Noam Nisan, Dana Ron
We present several results regarding randomized one-round communication complexity. Our results include a connection to the VC-dimension, a study of the problem of computing the inner product of two...
Automata Learning and its Applications (1995)
1 1 Introduction 3 1.1 The PAC Model and Some of its Extensions : : : : : : : : : : : : : : : : : : : : : : : 5 1.2 Background on Automata Learning : : : : : : : : : : : : : : : : : : : : : : : : : :...
On the Exact Learnability of Automata with Small Cover Time (1995)
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, 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 and Usage of Acyclic Probabilistic Finite Automata (1995)
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...
On Randomized One-Round Communication Complexity (1995)
Ilan Kremer, Noam Nisan, Dana Ron
We present several results regarding randomized oneround communication complexity. These include a connection to the VC-dimension, a study of the problem of computing the inner product of two real...
On the Learnability and Usage of Acyclic Probabilistic Finite Automata (1995)
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...
On the Learnability and Usage of Acyclic Probabilistic Finite Automata (1995)
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...
Learning to Model Sequences Generated by Switching Distributions (1995)
We study efficient algorithms for solving the following problem, which we call the switching distributions learning problem. A sequence S = oe 1 oe 2 : : : oe n , over a finite alphabet \Sigma is...
Learning to Model Sequences Generated By Switching Distributions (1995)
We study efficient algorithms for solving the following problem, which we call the switching distributions learning problem. A sequence S = oe 1 oe 2 : : : oe n , over a finite alphabet S is...
Exactly Learning Automata with Small Cover Time (1995)
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...
An Experimental and Theoretical Comparison of Model Selection Methods (1995)
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...
M.I.T. In the game theory literature, there is an intriguing line of research on the problem of playing a repeated matrix game
M.I.T. In the game theory literature, there is an intriguing line of research on the problem of playing a repeated matrix game
On the Learnability of Discrete Distributions (Extended Abstract) (1994)
Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
Dana Ron, Yoram Singer, Naftali Tishby
We propose a learning algorithm for a variable memory length Markov process. Human communication, whether given as text, handwriting, or speech, has multi characteristic time scales. On short scales...
On the Learnability of Discrete Distributions (Extended Abstract) (1994)
Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire
this paper, we concentrate on discrete distributions over f0; 1g
Learning Probabilistic Automata with Variable Memory Length (1994)
Dana Ron, Yoram Singer, Naftali Tishby
We propose and analyze a distribution learning algorithm for variable memory length Markov processes. These processes can be described by a subclass of probabilistic finite automata which we name...
Efficient Learning of Typical Finite Automata from Random Walks (1993)
Yoav Freund Att, Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, ...
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...
Efficient Learning of Typical Finite Automata from Random Walks (Extended Abstract) (1993)
Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
) Yoav Freund University of California Santa Cruz, CA 95064 Michael Kearns AT&T Bell Laboratories Murray Hill, NJ 07974 Dana Ron Hebrew University Jerusalem 91904, Israel Ronitt Rubinfeld Cornell...
Efficient Learning of Typical Finite Automata from Random Walks (1993)
Extend Ed, Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, ...
) Yoav Freund AT&T Research Murray Hill, NJ 07974 Michael Kearns AT&T Research Murray Hill, NJ 07974 Dana Ron MIT Cambridge, MA 02138 Ronitt Rubinfeld Cornell University Ithaca, NY 14853...
Efficient Learning of Typical Finite Automata from Random Walks (1993)
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...
Efficient Learning of Typical Finite Automata from Random Walks (1993)
Extend Ed, Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, ...
) Yoav Freund University of California Santa Cruz, CA 95064 Michael Kearns AT&T Bell Laboratories Murray Hill, NJ 07974 Dana Ron Hebrew University Jerusalem 91904, Israel Ronitt Rubinfeld Cornell...
Property Testing and its connection to Learning and Approximation
Oded Goldreich Shafi, 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...
Property Testing and Its Connection to Learning and Approximation
Oded Goldreich Shafi, 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...
An Experimental and Theoretical Comparison of Model Selection Methods
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...
An Experimental and Theoretical Comparison of Model Selection Methods
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...
An Experimental and Theoretical Comparison of Model Selection Methods
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...
Property Testing and its Connection to Learning and Approximation
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...
An Experimental and Theoretical Comparison of Model Selection Methods
Michael Kearns, Yishay Mansour, Andrew Y. Ng, Dana Ron
In the model selection problem... The goal of 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...