In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman
rozdział
Lecture Notes in Computer Science > Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation > Surveys > 302-332
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 → [0,1], we wish to estimate $2^{-n} \sum_{x\in\{0,1\}^n} f(x)$ upto an additive error of ε. We are allowed to employ a randomized algorithm that may err with probability at most δ. We survey known algorithms for this problem...
