Next: The Random Oracle Hypothesis
Up: The Technion Period (1986-94)
Previous: Bounds on Tradeoffs between
A key contribution of this paper is an algorithm for estimating
the average of (bounded) functions. The algorithm is optimal up-to
a constant factor both in its randomness and query complexity.
It consists of taking the median value of a sequence of values,
where the values are the averages over pairwise-independent sub-samples,
and the sub-samples are generated by a random walk on an expander graph.
Comments:
Authored by M. Bellare, O. Goldreich and S. Goldwasser. Appeared in
- Proc. of the 31st FOCS, pp. 563-572, 1990.
- Computational
Complexity, Vol. 4, No. 4 (1993), pp. 319-354.
Oded Goldreich
2003-07-30