All reports by Author Dana Ron:

__
TR21-133
| 12th September 2021
__

Oded Goldreich, Dana Ron#### Testing Distributions of Huge Objects

Revisions: 1

__
TR21-129
| 6th September 2021
__

Oded Goldreich, Dana Ron#### A Lower Bound on the Complexity of Testing Grained Distributions

__
TR20-068
| 3rd May 2020
__

Oded Goldreich, Dana Ron#### One-Sided Error Testing of Monomials and Affine Subspaces

Revisions: 1

__
TR18-185
| 6th November 2018
__

Yonatan Nakar, Dana Ron#### On the Testability of Graph Partition Properties

__
TR18-045
| 6th March 2018
__

Oded Goldreich, Dana Ron#### The Subgraph Testing Model

Revisions: 2

__
TR16-105
| 13th July 2016
__

Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron#### Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

Revisions: 1

__
TR15-046
| 2nd April 2015
__

Talya Eden, Amit Levi, Dana Ron#### Approximately Counting Triangles in Sublinear Time

Comments: 1

__
TR15-019
| 3rd February 2015
__

Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira#### Constructing Near Spanning Trees with Few Local Inspections

__
TR14-029
| 4th March 2014
__

Oded Goldreich, Dana Ron#### On Learning and Testing Dynamic Environments

Revisions: 3

__
TR13-109
| 11th August 2013
__

Oded Goldreich, Dana Ron#### On Sample-Based Testers

Revisions: 1

__
TR13-096
| 25th June 2013
__

Dana Ron, Rocco Servedio#### Exponentially improved algorithms and lower bounds for testing signed majorities

__
TR12-155
| 15th November 2012
__

Clement Canonne, Dana Ron, Rocco Servedio#### Testing probability distributions using conditional samples

Revisions: 1

__
TR12-101
| 10th August 2012
__

Oded Goldreich, Shafi Goldwasser, Dana Ron#### On the possibilities and limitations of pseudodeterministic algorithms

__
TR12-055
| 4th May 2012
__

Reut Levi, Dana Ron, Ronitt Rubinfeld#### Testing Similar Means

__
TR12-035
| 5th April 2012
__

Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler#### Finding Cycles and Trees in Sublinear Time

Revisions: 1
,
Comments: 1

__
TR11-078
| 9th May 2011
__

Dana Ron, Gilad Tsur#### On Approximating the Number of Relevant Variables in a Function

__
TR11-041
| 24th March 2011
__

Dana Ron, Gilad Tsur#### Testing Computability by Width-Two OBDDs

__
TR10-157
| 24th October 2010
__

Reut Levi, Dana Ron, Ronitt Rubinfeld#### Testing Properties of Collections of Distributions

Revisions: 1

__
TR09-083
| 24th September 2009
__

Dana Ron, Mira Gonen, Yuval Shavitt#### Counting Stars and Other Small Subgraphs in Sublinear Time

__
TR08-041
| 10th April 2008
__

Oded Goldreich, Dana Ron#### On Proximity Oblivious Testing

__
TR08-039
| 7th April 2008
__

Oded Goldreich, Dana Ron#### Algorithmic Aspects of Property Testing in the Dense Graphs Model

__
TR05-125
| 2nd November 2005
__

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith#### Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size

__
TR05-094
| 9th August 2005
__

Michal Parnas, Dana Ron#### On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms

Revisions: 1

__
TR05-073
| 14th July 2005
__

Oded Goldreich, Dana Ron#### Approximating Average Parameters of Graphs.

__
TR04-013
| 10th February 2004
__

Oded Goldreich, Dana Ron#### On Estimating the Average Degree of a Graph.

__
TR04-010
| 26th January 2004
__

Michal Parnas, Dana Ron, Ronitt Rubinfeld#### Tolerant Property Testing and Distance Approximation

__
TR03-033
| 6th May 2003
__

Meir Feder, Dana Ron, Ami Tavory#### Bounds on Linear Codes for Network Multicast

Comments: 1

__
TR01-063
| 5th August 2001
__

Michal Parnas, Dana Ron, Alex Samorodnitsky#### Proclaiming Dictators and Juntas or Testing Boolean Formulae

Revisions: 1

__
TR00-020
| 27th March 2000
__

Oded Goldreich, Dana Ron#### On Testing Expansion in Bounded-Degree Graphs

__
TR99-017
| 4th June 1999
__

Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky#### Improved Testing Algorithms for Monotonicity.

Revisions: 1

__
TR98-062
| 28th October 1998
__

Oded Goldreich, Dana Ron, Madhu Sudan#### Chinese Remaindering with Errors

Revisions: 4
,
Comments: 1

__
TR97-028
| 12th July 1997
__

Scott E. Decatur, Oded Goldreich, Dana Ron#### Computational Sample Complexity

__
TR96-057
| 18th November 1996
__

Oded Goldreich, Dana Ron#### Property Testing and its connection to Learning and Approximation

Oded Goldreich, Dana Ron

We initiate a study of a new model of property testing that is a hybrid of testing properties of distributions and testing properties of strings.

Specifically, the new model refers to testing properties of distributions, but these are distributions over huge objects (i.e., very long strings).

Accordingly, the ...
more >>>

Oded Goldreich, Dana Ron

A distribution is called $m$-grained if each element appears with probability that is an integer multiple of $1/m$.

We prove that, for any constant $c<1$, testing whether a distribution over $[\Theta(m)]$ is $m$-grained requires $\Omega(m^c)$ samples.

Oded Goldreich, Dana Ron

We consider the query complexity of three versions of the problem of testing monomials and affine (and linear) subspaces with one-sided error, and obtain the following results:

\begin{itemize}

\item The general problem, in which the arity of the monomial (resp., co-dimension of the subspace) is not specified, has ...
more >>>

Yonatan Nakar, Dana Ron

In this work we study the testability of a family of graph partition properties that generalizes a family previously studied by Goldreich, Goldwasser, and Ron (Journal of the ACM, 1998). While the family studied by Goldreich et al. includes a variety of natural properties, such as k-colorability and containing a ... more >>>

Oded Goldreich, Dana Ron

We initiate a study of testing properties of graphs that are presented as subgraphs of a fixed (or an explicitly given) graph.

The tester is given free access to a base graph $G=([\n],E)$, and oracle access to a function $f:E\to\{0,1\}$ that represents a subgraph of $G$.

The tester is ...
more >>>

Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron

The function $f\colon \{-1,1\}^n \to \{-1,1\}$ is a $k$-junta if it depends on at most $k$ of its variables. We consider the problem of tolerant testing of $k$-juntas, where the testing algorithm must accept any function that is $\epsilon$-close to some $k$-junta and reject any function that is $\epsilon'$-far from ... more >>>

Talya Eden, Amit Levi, Dana Ron

We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in two models: Exact counting algorithms, which require reading the entire graph, and streaming algorithms, where the edges are given in a stream and the memory is limited. In this work ... more >>>

Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let $G$ be a connected bounded-degree graph. Given an edge $e$ in $G$ we would like ... more >>>

Oded Goldreich, Dana Ron

We initiate a study of learning and testing dynamic environments,

focusing on environment that evolve according to a fixed local rule.

The (proper) learning task consists of obtaining the initial configuration

of the environment, whereas for non-proper learning it suffices to predict

its future values. The testing task consists of ...
more >>>

Oded Goldreich, Dana Ron

The standard definition of property testing endows the tester with the ability to make arbitrary queries to ``elements''

of the tested object.

In contrast, sample-based testers only obtain independently distributed elements (a.k.a. labeled samples) of the tested object.

While sample-based testers were defined by

Goldreich, Goldwasser, and Ron ({\em JACM}\/ ...
more >>>

Dana Ron, Rocco Servedio

A signed majority function is a linear threshold function $f : \{+1,1\}^n \to \{+1,1\}$ of the form

$f(x)={\rm sign}(\sum_{i=1}^n \sigma_i x_i)$ where each $\sigma_i \in \{+1,-1\}.$ Signed majority functions are a highly symmetrical subclass of the class of all linear threshold functions, which are functions of the form ${\rm ...
more >>>

Clement Canonne, Dana Ron, Rocco Servedio

We study a new framework for property testing of probability distributions, by considering distribution testing algorithms that have access to a conditional sampling oracle. \footnote{Independently from our work, Chakraborty et al. [CFGM13] also considered this framework. We discuss their work in Subsection 1.4.} This is an oracle that takes as ... more >>>

Oded Goldreich, Shafi Goldwasser, Dana Ron

We study the possibilities and limitations

of pseudodeterministic algorithms,

a notion put forward by Gat and Goldwasser (2011).

These are probabilistic algorithms that solve search problems

such that on each input, with high probability, they output

the same solution, which may be thought of as a canonical solution.

We consider ...
more >>>

Reut Levi, Dana Ron, Ronitt Rubinfeld

We consider the problem of testing a basic property of collections of distributions: having similar means. Namely, the algorithm should accept collections of distributions in which all distributions have means that do not differ by more than some given parameter, and should reject collections that are relatively far from having ... more >>>

Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler

(This is a revised version of work that was posted on arXiv in July 2010.)

We present sublinear-time (randomized) algorithms for finding simple cycles of length at least $k\geq3$ and tree-minors in bounded-degree graphs.

The complexity of these algorithms is related to the distance

of the graph from being ...
more >>>

Dana Ron, Gilad Tsur

In this work we consider the problem of approximating the number of relevant variables in a function given query access to the function. Since obtaining a multiplicative factor approximation is hard in general, we consider several relaxations of the problem. In particular, we consider relaxations in which we have a ... more >>>

Dana Ron, Gilad Tsur

Property testing is concerned with deciding whether an object

(e.g. a graph or a function) has a certain property or is ``far''

(for a prespecified distance measure) from every object with

that property. In this work we consider the property of being

computable by a read-once ...
more >>>

Reut Levi, Dana Ron, Ronitt Rubinfeld

We propose a framework for studying property testing of collections of distributions,

where the number of distributions in the collection is a parameter of the problem.

Previous work on property testing of distributions considered

single distributions or pairs of distributions. We suggest two models that differ

in the way the ...
more >>>

Dana Ron, Mira Gonen, Yuval Shavitt

Detecting and counting the number of copies of certain subgraphs (also known as {\em network motifs\/} or {\em graphlets\/}), is motivated by applications in a variety of areas ranging from Biology to the study of the World-Wide-Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of ... more >>>

Oded Goldreich, Dana Ron

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 parameters,

whereas the basic test is oblivious of the proximity parameter.

We refer to such basic ...
more >>>

Oded Goldreich, Dana Ron

In this paper we consider two refined questions regarding

the query complexity of testing graph properties

in the adjacency matrix model.

The first question refers to the relation between adaptive

and non-adaptive testers, whereas the second question refers to

testability within complexity that

is inversely proportional to ...
more >>>

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith

We raise the question of approximating compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and Lempel-Ziv (LZ), and present algorithms and lower bounds for approximating compressibility with respect to ... more >>>

Michal Parnas, Dana Ron

We consider the problem of estimating the size, $VC(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 $(\alpha,\eps)$-approximation algorithm

if it outputs with high probability an estimate $\widehat{VC}$

such that ...
more >>>

Oded Goldreich, Dana Ron

Inspired by Feige ({\em 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

and the average distance between pairs of vertices in a graph.

Since our focus is on sublinear algorithms, ...
more >>>

Oded Goldreich, 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 approximated

arbitrarily well in sublinear time, unless the graph is extremely sparse

(e.g., unless the graph has a sublinear ...
more >>>

Michal Parnas, Dana Ron, Ronitt Rubinfeld

A standard property testing algorithm is required to determine

with high probability whether a given object has property

P or whether it is \epsilon-far from having P, for any given

distance parameter \epsilon. An object is said to be \epsilon-far

from having ...
more >>>

Meir Feder, Dana Ron, Ami Tavory

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 code-construction complexity can be

gained by replacing these routing nodes by linear coding

nodes. These nodes transmit linear combinations ...
more >>>

Michal Parnas, Dana Ron, Alex Samorodnitsky

We consider the problem of determining whether a given

function f : {0,1}^n -> {0,1} belongs to a certain class

of Boolean functions F or whether it is far from the class.

More precisely, given query access to the function f and given

a distance parameter epsilon, we would ...
more >>>

Oded Goldreich, Dana Ron

We consider testing graph expansion in the bounded-degree graph model.

Specifically, we refer to algorithms for testing whether the graph

has a second eigenvalue bounded above by a given threshold

or is far from any graph with such (or related) property.

We present a natural algorithm aimed ... more >>>

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$, where

$\Sigma$ and $\Xi$ are finite ordered sets, the test always accepts a

monotone $f$, and rejects $f$ with high probability if it is $\e$-far

from being monotone (i.e., every ...
more >>>

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 < \prod_{i=1}^k p_i. Thus the residues of m modulo

relatively prime integers p_1 < p_2 < ... < p_n

form a redundant representation of m if ...
more >>>

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

sometimes seems to be required.

In addition, it has long been known that there are

concept classes ...
more >>>

Oded Goldreich, Dana Ron

In this paper, we consider the question of determining whether

a function $f$ has property $P$ or is $\e$-far from any

function with property $P$.

The property testing algorithm is given a sample of the value

of $f$ on instances drawn according to some distribution.

In some cases,

more >>>