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