Back to Search
Start Over
Optimal Communication Rates and Combinatorial Properties for Common Randomness Generation.
- Source :
- IEEE Transactions on Information Theory; Dec2021, Vol. 67 Issue 12, p7723-7739, 17p
- Publication Year :
- 2021
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- COMMONS
LINEAR programming
HYPERGRAPHS
DISTRIBUTED algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 67
- Issue :
- 12
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 153731628
- Full Text :
- https://doi.org/10.1109/TIT.2021.3119976