Next: Approximations of General Independent
Up: The Technion Period (1986-94)
Previous: The Random Oracle Hypothesis
In retrospect, the most intesresting contributions of this work are
two-party and multi-party fault-tolerant protocols for sampling in a
predetermined universe. Specifically, in the two-party protocol,
for any subset of the universe, no party may force the outcome to
reside in this subset with probability greater than the square
root of the density of this subset.
Comments:
Authored by O. Goldreich, S. Goldwasser and N. Linial. Appeared in
- Proc. of the 32nd FOCS, pp. 447-457, 1991.
- SIAM
Jour. on Comp., Volume 27, Number 2, April 1998, Pages 506-544.
Oded Goldreich
2003-07-30