Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR97-020 | 15th May 1997 00:00

#### A Sample of Samplers -- A Computational Perspective on Sampling (survey).

TR97-020
Authors: Oded Goldreich
Publication: 16th May 1997 09:06
Keywords:

Abstract:

We consider the problem of estimating the average of a huge set of values.
That is,
given oracle access to an arbitrary function $f:\{0,1\}^n\mapsto[0,1]$,
we need to estimate $2^{-n} \sum_{x\in\{0,1\}^n} f(x)$
upto an additive error of $\epsilon$.
We are allowed to employ a randomized algorithm which may err
with probability at most $\delta$.

We survey known algorithms for this problem
and focus on the ideas underlying their construction.
In particular, we present an
algorithm which makes $O(\epsilon^{-2} \cdot \log(1/\delta))$ queries
and uses $n+O(\log(1/\epsilon))+O(\log(1/\delta))$ coin tosses,
both complexities being very close to the corresponding lower bounds.

ISSN 1433-8092 | Imprint