Dana Ron

Dana Ron

Auto-generated profile, based on publicly available information

Dana Ron

Tel Aviv University, Tel-Aviv, Israel

Research Focus & Metrics

Academic Career Length

34Years (1993-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 July 1998 in Journal of the ACM
Verified
Journal Article
Open access
OGOded Goldreich
Oded Goldreich
SGShari Goldwasser
Shari Goldwasser
DRDana Ron
Dana Ron
In this paper, we consider the question of determining whether a function f has property P or is ε-far from any function with property P. A property testing algorithm is given a sample of the value of f on instances drawn according to some distribution. In some cases, it is also allowed to query f on instances of its choice. We study this question for different properties and establish some connections to problems in learning theory and approximation. In particular, we focus our attention on testing graph properties. Given access to a graph G in the form of being able to query whether an edge exists or not between a pair of vertices, we devise algorithms to test whether the underlying graph has properties such as being bipartite, k -Colorable, or having a p -Clique (clique of density p with respect to the vertex set). Our graph property testing algorithms are probabilistic and make assertions that are correct with high probability, while making a number of queries that is independent of the size of the graph. Moreover, the property testing algorithms can be used to efficiently (i.e., in time linear in the number of vertices) construct partitions of the graph that correspond to the property being tested, if it holds for the input graph.

1 August 1999 in Neural Computation
Verified
Journal Article
Closed access
MKMichael Kearns
Michael Kearns
DRDana Ron
Dana Ron
In this article we prove sanity-check bounds for the error of the leave-oneout cross-validation estimate of the generalization error: that is, bounds showing that the worst-case error of this estimate is not much worse than that of the training error estimate. The name sanity check refers to the fact that although we often expect the leave-one-out estimate to perform considerably better than the training error estimate, we are here only seeking assurance that its performance will not be considerably worse. Perhaps surprisingly, such assurance has been given only for limited cases in the prior literature on cross-validation. Any nontrivial bound on the error of leave-one-out must rely on some notion of algorithmic stability. Previous bounds relied on the rather strong notion of hypothesis stability, whose application was primarily limited to nearest-neighbor and other local algorithms. Here we introduce the new and weaker notion of error stability and apply it to obtain sanity-check bounds for leave-one-out for other classes of learning algorithms, including training error minimization procedures and Bayesian algorithms. We also provide lower bounds demonstrating the necessity of some form of error stability for proving bounds on the error of the leave-one-out estimate, and the fact that for training error minimization algorithms, in the worst case such bounds must still depend on the Vapnik-Chervonenkis dimension of the hypothesis class.

1 January 2003 in SIAM Journal on Computing
Verified
Journal Article
Closed access
GEGuy Even
Guy Even
ZLZvi Lotker
Zvi Lotker
DRDana Ron
Dana Ron
SSShakhar Smorodinsky
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 input of the min-CF-coloring problem is a set system $(X,{\cal S})$, where each $S \in {\cal S}$ is a subset of X. The output is a coloring $\chi$ of the sets in ${\cal S}$ that satisfies the following constraint: for every $x \in X$ there exists a color i and a unique set $S \in {\cal S}$ such that $x \in S$ and $\chi(S) = i$. The goal is to minimize the number of colors used by the coloring $\chi$. Min-CF-coloring of general set systems is not easier than the classic graph coloring problem. However, in view of our motivation, we consider set systems induced by simple geometric regions in the plane. In particular, we study disks (both congruent and noncongruent), axis-parallel rectangles (with a constant ratio between the smallest and largest rectangle), regular hexagons (with a constant ratio between the smallest and largest hexagon), and general congruent centrally symmetric convex regions in the plane. In all cases we have coloring algorithms that use O(log n) colors (where n is the number of regions). Tightness is demonstrated by showing that even in the case of unit disks, $\Theta(\log n)$ colors may be necessary. For rectangles and hexagons we also obtain a constant-ratio approximation algorithm when the ratio between the largest and smallest rectangle (hexagon) is a constant. We also consider a dual problem of CF-coloring points with respect to sets. Given a set system $(X,{\cal S})$, the goal in the dual problem is to color the elements in X with a minimum number of colors so that every set $S \in {\cal S}$ contains a point whose color appears only once in S. We show that O(log |X|) colors suffice for set systems in which X is a set of points in the plane and the sets are intersections of X with scaled translations of a convex region. This result is used in proving that O(log n) colors suffice in the primal version.

1 September 2006 in Journal of Computer and System Sciences
Verified
Journal Article
Closed access
MPMichal Parnas
Michal Parnas
DRDana Ron
Dana Ron
RRRonitt Rubinfeld
Ronitt Rubinfeld

1 August 2007 in Theoretical Computer Science
Verified
Journal Article
Closed access
MPMichal Parnas
Michal Parnas
DRDana Ron
Dana Ron

1 June 1999 in computational complexity
Verified
Journal Article
Closed access
PDF file
IKI. Kremer
I. Kremer
NNN. Nisan
N. Nisan
DRD. Ron
D. Ron