All reports by Author Reut Levi:

__
TR15-019
| 3rd February 2015
__

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

__
TR12-055
| 4th May 2012
__

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

__
TR11-171
| 15th December 2011
__

Piotr Indyk, Reut Levi, Ronitt Rubinfeld#### Approximating and Testing $k$-Histogram Distributions in Sub-linear time

Revisions: 1

__
TR10-157
| 24th October 2010
__

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

Revisions: 1

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

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

Piotr Indyk, Reut Levi, Ronitt Rubinfeld

A discrete distribution $p$, over $[n]$, is a $k$-histogram if its probability distribution function can be

represented as a piece-wise constant function with $k$ pieces. Such a function

is

represented by a list of $k$ intervals and $k$ corresponding values. We consider

the following problem: given a collection of samples ...
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 >>>