ECCC-Report TR06-026https://eccc.weizmann.ac.il/report/2006/026Comments and Revisions published for TR06-026en-usTue, 28 Feb 2006 18:39:40 +0200
Paper TR06-026
| Random Selection with an Adversarial Majority |
Ronen Gradwohl,
Salil Vadhan,
David Zuckerman
https://eccc.weizmann.ac.il/report/2006/026We consider the problem of random selection, where $p$ players follow a protocol to jointly select a random element of a universe of size $n$. However, some of the players may be adversarial and collude to force the output to lie in a small subset of the universe. We describe essentially the first protocols that solve this problem in the presence of a dishonest majority in the full-information model (where the adversary is computationally unbounded and all communication is via broadcast). Our protocols are nearly optimal in several parameters, including the round complexity (as a function of $n$), the randomness complexity, the communication complexity, and the tradeoffs between the fraction of honest players, the probability that the output lies in a small subset of the universe, and the density of this subset.
Tue, 28 Feb 2006 18:39:40 +0200https://eccc.weizmann.ac.il/report/2006/026