ECCC-Report TR97-020https://eccc.weizmann.ac.il/report/1997/020Comments and Revisions published for TR97-020en-usFri, 16 May 1997 09:06:30 +0300
Paper TR97-020
| A Sample of Samplers -- A Computational Perspective on Sampling (survey). |
Oded Goldreich
https://eccc.weizmann.ac.il/report/1997/020
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.
Fri, 16 May 1997 09:06:30 +0300https://eccc.weizmann.ac.il/report/1997/020