Optimal Communication Rates and Combinatorial Properties for Common Randomness Generation

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

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)7723-7739
Number of pages17
JournalIEEE Transactions on Information Theory
Issue number12
StatePublished - Dec 1 2021


  • Common randomness
  • blackboard communication
  • combinatorics
  • hypergraph connectivity
  • optimal communication rate

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Optimal Communication Rates and Combinatorial Properties for Common Randomness Generation'. Together they form a unique fingerprint.

Cite this