Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Ronitt Rubinfeld:

TR15-019 | 3rd February 2015
Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira

Constructing Near Spanning Trees with Few Local Inspections

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

TR14-021 | 18th February 2014
Clement Canonne, Ronitt Rubinfeld

Testing probability distributions underlying aggregated data

In this paper, we analyze and study a hybrid model for testing and learning probability distributions. Here, in addition to samples, the testing algorithm is provided with one of two different types of oracles to the unknown distribution $D$ over $[n]$. More precisely, we define both the dual and extended ... more >>>

TR12-055 | 4th May 2012
Reut Levi, Dana Ron, Ronitt Rubinfeld

Testing Similar Means

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

TR11-171 | 15th December 2011
Piotr Indyk, Reut Levi, Ronitt Rubinfeld

Approximating and Testing $k$-Histogram Distributions in Sub-linear time

Revisions: 1

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
represented by a list of $k$ intervals and $k$ corresponding values. We consider
the following problem: given a collection of samples ... more >>>

TR11-013 | 3rd February 2011
Ronitt Rubinfeld, Asaf Shapira

Sublinear Time Algorithms

Sublinear time algorithms represent a new paradigm
in computing, where an algorithm must give some sort
of an answer after inspecting only a very small portion
of the input. We discuss the types of answers that
one can hope to achieve in this setting.

more >>>

TR10-157 | 24th October 2010
Reut Levi, Dana Ron, Ronitt Rubinfeld

Testing Properties of Collections of Distributions

Revisions: 1

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

TR10-027 | 28th February 2010
Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant

Testing monotonicity of distributions over general partial orders

We investigate the number of samples required for testing the monotonicity of a distribution with respect to an arbitrary underlying partially ordered set. Our first result is a nearly linear lower bound for the sample complexity of testing monotonicity with respect to the poset consisting of a directed perfect matching. ... more >>>

ISSN 1433-8092 | Imprint