We study common randomness generation problems where $n$ players aim to generate same sequences of random coin flips where some subsets of the players share an independent common coin which can be tossed multiple times, and there is a publicly seen blackboard through which the players communicate with each other. We provide a tight representation of the optimal communication rates via linear programming, and more importantly, propose explicit algorithms for the optimal distributed simulation for a wide class of hypergraphs. In particular, the optimal communication rate in complete hypergraphs is still achievable in sparser hypergraphs containing a path-connected cycle-free cluster of topologically connected components. Some key steps in analyzing the upper bounds rely on two different definitions of connectivity in hypergraphs, which may be of independent interest.
翻译:我们研究的是常见的随机生成问题,即一美元玩家的目标是生成相同的随机硬币翻转序列,即某些子集玩家共享一个独立的共同硬币,可以多次抛掷,并且有一个公开可见的黑板,让玩家通过黑板相互交流。我们通过线性编程对最佳通信率进行严密的表述,更重要的是,为一系列广泛的高音进行最佳分布模拟提出明确的算法。 特别是,完整高音中的最佳通信率仍然可以在稀疏的高音中实现,高音中含有一条与路径相连的循环连接的、与地形有关的组件组合。 分析上界的一些关键步骤依赖于两个不同的连接定义,这些定义可能是独立的。