Name
Abstract | ||
|---|---|---|
We consider the problem of random selection, where p play- ers follow a protocol to jointly select a random element of a universe of size n. However, some of the players may be adversarial and col- lude to force the output to lie in a small subset of the universe. We describe essentially the flrst 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 non-simultaneous 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 tradeofis 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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11818175_25 | Electronic Colloquium on Computational Complexity (ECCC) |
Field | DocType | Volume |
Computer science,Theoretical computer science,Sampling (statistics),Adversarial system | Journal | 13 |
Issue | ISSN | ISBN |
026 | 0302-9743 | 3-540-37432-9 |
Citations | PageRank | References |
17 | 0.86 | 35 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ronen Gradwohl | 1 | 70 | 7.84 |
| Salil P. Vadhan | 2 | 4676 | 234.84 |
| David Zucherman | 3 | 2588 | 266.65 |