We study the distributed simulation problem where @math players aim to generate 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.
@cite_18: The focus of this paper is on the public communication required for generating a maximal-rate secret key (SK) within the multiterminal source model of Csiszar and Narayan. Building on the prior work of Tyagi for the two-terminal scenario, we derive a lower bound on the communication complexity, @math , defined to be the minimum rate of public communication needed to generate a maximal-rate SK. It is well known that the minimum rate of communication for omniscience, denoted by @math , is an upper bound on @math . For the class of pairwise independent network (PIN) models defined on uniform hypergraphs, we show that a certain Type @math condition, which is verifiable in polynomial time, guarantees that our lower bound on @math meets the @math upper bound. Thus, the PIN models satisfying our condition are @math -maximal, indicating that the upper bound @math holds with equality. This allows us to explicitly evaluate @math for such PIN models. We also give several examples of PIN models that satisfy our Type @math condition. Finally, we prove that for an arbitrary multiterminal source model, a stricter version of our Type @math condition implies that communication from all terminals (omnivocality) is needed for establishing an SK of maximum rate. For three-terminal source models, the converse is also true: omnivocality is needed for generating a maximal-rate SK only if the strict Type @math condition is satisfied. However, for the source models with four or more terminals, counterexamples exist showing that the converse does not hold in general.
A related work deserving special attention is @cite_18 , which studied the also on hypergraphs. Specifically, it showed that if the @math -uniform hypergraph is (a notion introduced in @cite_18 ), then there is a strategy achieving the optimal communication rate @math and outputting each hyperedge . Our work differs from @cite_18 in the following aspects. First, instead of outputting each hyperedge exactly once, we may output a subset of hyperedges or some hyperedges with different repetitions (cf. Section ). Consequently, our lower bound in Theorem is stronger. Second, the achievability scheme in @cite_18 requires large blocklengths to achieve some small probability of error, while our achievability scheme is more combinatorial and achieves zero error. Third, their type @math condition is an information-theoretic condition, with an unclear relationship to combinatorial hypergraph theory. It is also unknown whether it can be verified in polynomial time that some subset of (possibly repeated) hyperedges in a given hypergraph forms a hypergraph of type @math . In contrast, our conditions in Theorems and are more combinatorial in nature, and the topological connectivity can be efficiently checked using matrix ranks. Hence, our work presents an alternative approach which sheds more lights on the combinatorial perspective.