Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2405.05211 · IEEE International Symposium on Information Theory (ISIT)

Broadcast Channel Synthesis from Shared Randomness

Malhar A. Managoli, Vinod M. Prabhakaran

Published Jul 7, 2024• 2 citations
arXivHTMLPDF

Abstract

We study the problem of synthesising a two-user broadcast channel using a common message, where each output terminal shares an independent source of randomness with the input terminal. This generalises two problems studied in the literature (Cuff, IEEE Trans. Inform. Theory, 2013; Kurri et.al., IEEE Trans. Inform. Theory, 2021). We give an inner bound on the tradeoff region between the rates of communication and shared randomness, and a lower bound on the minimum communication rate. Although the bounds presented here are not tight in general, they are tight for some special cases, including the aforementioned problems.

DOI
10.1109/isit57864.2024.10619094

Related papers

Exact Channel Synthesis

Lei Yu, Vincent Y. F. Tan

We consider the exact channel synthesis problem. This problem concerns the determination of the amount of information required to create exact correlation remotely when there is a certain rate of randomness shared by two terminals. This problem generalizes an existing approximate version, in which the generated joint distribution is restricted to be close to a target distribution under the total variation (TV) distance measure, instead being exactly equal to the target distribution. We provide single-letter inner and outer bounds on the admissible region of the shared randomness rate and the communication rate for the exact channel synthesis problem. These two bounds coincide for doubly symmetric binary sources, which implies that for such sources, the admissible rate region is completely characterized. We observe that for such sources, the admissible rate region for exact channel synthesis is strictly included in that for TV-approximate version.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•2 citations

Exact Channel Synthesis

Lei Yu, Vincent Y. F. Tan

We consider the exact channel synthesis problem. This problem concerns the determination of the minimum amount of information required to create exact correlation remotely when there is a certain rate of randomness shared by two terminals. This problem generalizes an existing approximate version, in which the generated joint distribution is required to be close to a target distribution under the total variation (TV) distance measure (instead being exactly equal to the target distribution). We provide single-letter inner and outer bounds on the admissible region of the shared randomness rate and the communication rate for the exact channel synthesis problem. These two bounds coincide for doubly symmetric binary sources. We observe that for such sources, the admissible rate region for exact channel synthesis is strictly included in that for the TV-approximate version. We also extend the exact and TV-approximate channel synthesis problems to sources with countably infinite alphabets and continuous sources; the latter includes Gaussian sources. As by-products, lemmas concerning soft-covering under Rényi divergence measures are derived.

IEEE Transactions on Information Theory•Oct 1, 2019•18 citations

Exact Channel Synthesis

Lei Yu, Vincent Y. F. Tan

We consider the exact channel synthesis problem. This problem concerns the determination of the minimum amount of information required to create exact correlation remotely when there is a certain rate of randomness shared by two terminals. This problem generalizes an existing approximate version, in which the generated joint distribution is required to be close to a target distribution under the total variation (TV) distance measure (instead being exactly equal to the target distribution). We provide single-letter inner and outer bounds on the admissible region of the shared randomness rate and the communication rate for the exact channel synthesis problem. These two bounds coincide for doubly symmetric binary sources. We observe that for such sources, the admissible rate region for exact channel synthesis is strictly included in that for the TV-approximate version. We also extend the exact and TV-approximate channel synthesis problems to sources with countably infinite alphabets and continuous sources; the latter includes Gaussian sources. As by-products, lemmas concerning soft-covering under Rényi divergence measures are derived.

arXiv:1810.13246•Oct 30, 2018•2 citations

Secure Cascade Channel Synthesis

Sanket Satpathy, Paul Cuff

We consider the problem of generating correlated random variables in a distributed fashion, where communication is constrained to a cascade network. The first node in the cascade observes an i.i.d. sequence$X^{n}$locally before initiating communication along the cascade. All nodes share bits of common randomness that are independent of$X^{n}$. We consider secure synthesis—random variables produced by the system appear to be appropriately correlated and i.i.d. even to an eavesdropper who is cognizant of the communication transmissions. We characterize the optimal tradeoff between the amount of common randomness used and the required rates of communication. We find that not only does common randomness help, its usage exceeds the communication rate requirements. The most efficient scheme is based on a superposition codebook, with the first node selecting messages for all downstream nodes. We also provide a fleeting view of related problems, demonstrating how the optimal rate region may shrink or expand.

arXiv:1305.4314•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•25 citations

Exact Common Information and Exact Channel Synthesis for Correlated Gaussian Sources

Lei Yu

In this paper, we resolve two conjectures posed by Yu and Tan in 2020 (in two separate papers published in the IEEE Trans. Inf. Theory). Specifically, we establish that: 1) the exact common information for a pair of $ρ$-correlated Gaussian sources is given by the conjectured expression $\frac{1}{2}\log\frac{1+ρ}{1-ρ}+\fracρ{1+ρ}$; and 2) the admissible region for the shared randomness rate and the communication rate in exact channel synthesis is exactly the conjectured one. These results yield two important consequences. First, for any $ρ>0$, the exact common information of a correlated Gaussian pair strictly exceeds Wyner's common information. Second, for $ρ>0$, the exact channel synthesis of such a pair requires strictly higher rates than the total-variation version. The proof combines an exact optimal-transport representation of the worst-case Gaussian cross-entropy, Fathi's Gaussian transport inequality, and a determinant inequality arising from the covariance structure of the conditional means.

arXiv:2608.26012•Aug 26, 2026•0 citations

Common Randomness Generation from Finite Compound Sources

Rami Ezzine, Moritz Wiese, Christian Deppe +1 more

We investigate the problem of generating common randomness (CR) from finite compound sources aided by unidirectional communication over rate-limited perfect channels. The two communicating parties, often referred to as terminals, observe independent and identically distributed (i.i.d.) samples of a finite compound source and aim to agree on a common random variable with a high probability for every possible realization of the source state. Both parties know the set of source states as well as their statistics. However, they are unaware of the actual realization of the source state. We establish a single-letter lower and upper bound on the compound CR capacity for the specified model. Furthermore, we present two special scenarios where the established bounds coincide.

arXiv:2401.14323•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•3 citations
We study the problem of synthesising a two-user broadcast channel using a common message, where each output terminal shares an independent source of randomness with the input terminal. This generalises two problems studied in the literature (Cuff, IEEE Trans. Inform. Theory, 2013; Kurri et.al., IEEE Trans. Inform. Theory, 2021). We give an inner bound on the tradeoff region between the rates of communication and shared randomness, and a lower bound on the minimum communication rate. Although the bounds presented here are not tight in general, they are tight for some special cases, including the aforementioned problems.
We consider the exact channel synthesis problem. This problem concerns the determination of the amount of information required to create exact correlation remotely when there is a certain rate of randomness shared by two terminals. This problem generalizes an existing approximate version, in which the generated joint distribution is restricted to be close to a target distribution under the total variation (TV) distance measure, instead being exactly equal to the target distribution. We provide single-letter inner and outer bounds on the admissible region of the shared randomness rate and the communication rate for the exact channel synthesis problem. These two bounds coincide for doubly symmetric binary sources, which implies that for such sources, the admissible rate region is completely characterized. We observe that for such sources, the admissible rate region for exact channel synthesis is strictly included in that for TV-approximate version.
We consider the exact channel synthesis problem. This problem concerns the determination of the minimum amount of information required to create exact correlation remotely when there is a certain rate of randomness shared by two terminals. This problem generalizes an existing approximate version, in which the generated joint distribution is required to be close to a target distribution under the total variation (TV) distance measure (instead being exactly equal to the target distribution). We provide single-letter inner and outer bounds on the admissible region of the shared randomness rate and the communication rate for the exact channel synthesis problem. These two bounds coincide for doubly symmetric binary sources. We observe that for such sources, the admissible rate region for exact channel synthesis is strictly included in that for the TV-approximate version. We also extend the exact and TV-approximate channel synthesis problems to sources with countably infinite alphabets and continuous sources; the latter includes Gaussian sources. As by-products, lemmas concerning soft-covering under Rényi divergence measures are derived.
We consider the exact channel synthesis problem. This problem concerns the determination of the minimum amount of information required to create exact correlation remotely when there is a certain rate of randomness shared by two terminals. This problem generalizes an existing approximate version, in which the generated joint distribution is required to be close to a target distribution under the total variation (TV) distance measure (instead being exactly equal to the target distribution). We provide single-letter inner and outer bounds on the admissible region of the shared randomness rate and the communication rate for the exact channel synthesis problem. These two bounds coincide for doubly symmetric binary sources. We observe that for such sources, the admissible rate region for exact channel synthesis is strictly included in that for the TV-approximate version. We also extend the exact and TV-approximate channel synthesis problems to sources with countably infinite alphabets and continuous sources; the latter includes Gaussian sources. As by-products, lemmas concerning soft-covering under Rényi divergence measures are derived.
We consider the problem of generating correlated random variables in a distributed fashion, where communication is constrained to a cascade network. The first node in the cascade observes an i.i.d. sequenceXnX^{n}Xnlocally before initiating communication along the cascade. All nodes share bits of common randomness that are independent ofXnX^{n}Xn. We consider secure synthesis—random variables produced by the system appear to be appropriately correlated and i.i.d. even to an eavesdropper who is cognizant of the communication transmissions. We characterize the optimal tradeoff between the amount of common randomness used and the required rates of communication. We find that not only does common randomness help, its usage exceeds the communication rate requirements. The most efficient scheme is based on a superposition codebook, with the first node selecting messages for all downstream nodes. We also provide a fleeting view of related problems, demonstrating how the optimal rate region may shrink or expand.
In this paper, we resolve two conjectures posed by Yu and Tan in 2020 (in two separate papers published in the IEEE Trans. Inf. Theory). Specifically, we establish that: 1) the exact common information for a pair of ρρρ-correlated Gaussian sources is given by the conjectured expression 12log⁡1+ρ1−ρ+ρ1+ρ\frac{1}{2}\log\frac{1+ρ}{1-ρ}+\fracρ{1+ρ}21​log1−ρ1+ρ​+1+ρρ​; and 2) the admissible region for the shared randomness rate and the communication rate in exact channel synthesis is exactly the conjectured one. These results yield two important consequences. First, for any ρ>0ρ>0ρ>0, the exact common information of a correlated Gaussian pair strictly exceeds Wyner's common information. Second, for ρ>0ρ>0ρ>0, the exact channel synthesis of such a pair requires strictly higher rates than the total-variation version. The proof combines an exact optimal-transport representation of the worst-case Gaussian cross-entropy, Fathi's Gaussian transport inequality, and a determinant inequality arising from the covariance structure of the conditional means.
We investigate the problem of generating common randomness (CR) from finite compound sources aided by unidirectional communication over rate-limited perfect channels. The two communicating parties, often referred to as terminals, observe independent and identically distributed (i.i.d.) samples of a finite compound source and aim to agree on a common random variable with a high probability for every possible realization of the source state. Both parties know the set of source states as well as their statistics. However, they are unaware of the actual realization of the source state. We establish a single-letter lower and upper bound on the compound CR capacity for the specified model. Furthermore, we present two special scenarios where the established bounds coincide.