next up previous
Next: Approximations of General Independent Up: The Technion Period (1986-94) Previous: The Random Oracle Hypothesis

Fault-tolerant Computations without Assumptions: the Two-party Case

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



Oded Goldreich
2003-07-30