Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PAIRWISE INDEPENDENT RANDOM VARIABLES:
Reports tagged with pairwise independent random variables:
TR97-020 | 15th May 1997
Oded Goldreich

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


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




ISSN 1433-8092 | Imprint