Random Selection with an Adversarial Majority
Random Selection with an Adversarial Majority
复制标题
对抗性多数的随机选择
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
David Zuckerman
中科院分区：
文献类型：
--
作者：
R. Gradwohl;S. Vadhan;David Zuckerman
我们考虑随机选择问题，其中p个玩家遵循一个协议，共同选择大小为n的宇宙中的一个随机元素。然而，一些参与者可能是敌对的，他们合谋迫使输出位于宇宙的一个小子集中。我们基本上描述的第一个协议，解决这个问题的存在下，一个不诚实的大多数在全信息模型（对手是计算无界，所有的通信是通过非同步广播）。我们的协议在几个参数中几乎是最优的，包括轮复杂度（作为n的函数），随机性复杂度，通信复杂度，以及诚实玩家的分数之间的权衡，输出位于宇宙的一个小子集中的概率，以及这个子集的密度。
We 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 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 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.