## A Computational Perspective on Sampling (survey)

#### Webpage for a survey by Oded Goldreich

#### 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\to[0,1]$,
we wish 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 that 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 that 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.

#### Preface

The idea of writing this survey occurred to me when finding out
that a brilliant, young researcher who has worked in very related areas
was unaware of the Median-of-Averages Sampler.
It then occurred to me that many of the results surveyed here
have appeared in papers devoted to other subjects
(indeed, the Median-of-Averages Sampler is an excellent example),
and have thus escaped the attention of a wider community,
which might have cared to know about them.
I thus decided to write a survey that focuses on these very basics.

#### Material available on-line

- First version posted:
May 1997.
- Revisions:
July 2010.
This revision includes a quantitative improvement
in Theorem 6.1, which is obtained by the subsequent work of [RVW].
Also included (as a new Section 7), is an alternative perspective
advocated by Ronen Shaltiel and Amnon Ta-Shma.

Back to
either Oded Goldreich's homepage
or general list of papers.