The Johnson-Lindenstrauss transform is a dimensionality reduction technique with a wide
range of applications to theoretical computer science. It is specified by a distribution over …

In this paper we study the problem of estimating the size of the union of sets S_1,\dots,S_M
where each set S_i⊆Ømega (for some discrete universe Ømega) is implicitly presented and …

We consider the estimation of aggregates over a data stream of multidimensional axis-
aligned rectangles. Rectangles are a basic primitive object in spatial databases, and …

Constraint satisfaction problems (CSPs) and data stream models are two powerful
abstractions to capture a wide variety of problems arising in different domains of computer …

Given a family of sets (S1, S2,... SM) over a universe Ω, estimating the size of their union in
the data streaming model is a fundamental computational problem with a wide variety of …

Estimating the size of the union of a stream of sets S₁, S₂,…, S_M where each set is a
subset of a known universe Ω is a fundamental problem in data streaming. This problem …

Constraint satisfaction problems (CSP's) and data stream models are two powerful
abstractions to capture a wide variety of problems arising in different domains of computer …

Efficient range-summability (ERS) of a long list of random variables is a fundamental
algorithmic problem that has applications to three important database applications, namely …

Given a stream of rectangles over a discrete space, we consider the problem of computing
the total number of distinct points covered by the rectangles. This is the discrete version of …

We show the following transformation: any two-party protocol for outputting a (1+ ε)-
approximation to f (x, y)=∑ j= 1n g (xj, yj) with probability at least 2/3, for any non-negative …