Optimal Communication Rates and Combinatorial Properties for Common Randomness Generation

DOI10.1109/TIT.2021.3119976MaRDI QIDQ5032612zbMATH OpenOpenAlexFDO

Authors Yanjun Han, Kedar Tatwawadi, Gowtham R. Kurri, Zhengqing Zhou, Vinod M. Prabhakaran, Tsachy Weissman

Publication date 17 February 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.03271

zbMATH Keywords

common randomness generationoptimal communication rates

Mathematics Subject Classification ID

Communication theory (94A05) Cryptography (94A60)

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.

Cited in

(4)

• Common Randomness and Secret Key Capacities of Two-Way Channels
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• scientific article; zbMATH DE number 1769898 (Why is no real title available?)
• The Power of Shared Randomness in Uncertain Communication

This page was built for publication: Optimal Communication Rates and Combinatorial Properties for Common Randomness Generation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5032612)