| Paper ID | D4-S7-T1.2 |
| Paper Title |
Optimal Communication Rates and Combinatorial Properties for Common Randomness Generation |
| Authors |
Yanjun Han, Kedar Tatwawadi, Stanford University, United States; Gowtham R. Kurri, Arizona State University, United States; Zhengqing Zhou, Stanford University, United States; Vinod M. Prabhakaran, Tata Institute of Fundamental Research, India; Tsachy Weissman, Stanford University, United States |
| Session |
D4-S7-T1: Common Randomness Generation |
| Chaired Session: |
Friday, 16 July, 00:00 - 00:20 |
| Engagement Session: |
Friday, 16 July, 00:20 - 00:40 |
| Abstract |
We study the distributed simulation problem 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.
|
