TY - GEN
T1 - Optimal Communication Rates and Combinatorial Properties for Common Randomness Generation
AU - Han, Yanjun
AU - Tatwawadi, Kedar
AU - Kurri, Gowtham R.
AU - Zhou, Zhengqing
AU - Prabhakaran, Vinod M.
AU - Weissman, Tsachy
N1 - Funding Information:
Y. Han and K. Tatwawadi contribute equally to this paper. GK and VP were supported by the Department of Atomic Energy, Government of India, under project no. RTI4001. This work was done while G. R. Kurri was at the Tata Institute of Fundamental Research.
Publisher Copyright:
© 2021 IEEE.
PY - 2021/7/12
Y1 - 2021/7/12
N2 - We study the distributed simulation problem where n players aim to generate same sequences of random coin flips, and some subsets of the players share an independent common coin which can be tossed multiple times. The players communicate with each other via a publicly seen blackboard. 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.
AB - We study the distributed simulation problem where n players aim to generate same sequences of random coin flips, and some subsets of the players share an independent common coin which can be tossed multiple times. The players communicate with each other via a publicly seen blackboard. 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.
UR - http://www.scopus.com/inward/record.url?scp=85115106714&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115106714&partnerID=8YFLogxK
U2 - 10.1109/ISIT45174.2021.9518090
DO - 10.1109/ISIT45174.2021.9518090
M3 - Conference contribution
AN - SCOPUS:85115106714
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1931
EP - 1936
BT - 2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2021 IEEE International Symposium on Information Theory, ISIT 2021
Y2 - 12 July 2021 through 20 July 2021
ER -