$next$ $up$ $previous$
Next: On the Complexity of Up: The Post-Doctoral Period (1983-86) Previous: On the Cryptographic Applications

On the Power of Two-Point Based Sampling

It is shown that a sequence of pairwise-independent samples, which can be constructed based on randomness proportional to the amount required to generate two samples, can be used to approximate the average of any function defined over the corresponding domain.

$\fbox{\begin{minipage}{40em} {\bf Abstract ({v.o.}):} {The purpose of this note... ...ct, with high probability, any set of non-negligible density.} \end{minipage}}$

Comments: Authored by B. Chor and O. Goldreich. Appeared in

Jour. of Complexity, Vol 5, 1989, pp. 96-106.

Oded Goldreich
2003-07-30