Oded Goldreich

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