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:1810.13246

Exact Channel Synthesis

Lei Yu, Vincent Y. F. Tan

Published Oct 30, 2018• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1810.13246

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 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 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 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

Exact Common Information and Exact Channel Synthesis for Correlated Discrete Sources

Lei Yu

In this paper, we provide a single-letter characterization of the exact common information for a pair of correlated discrete sources, as well as a single-letter characterization of the admissible region for the shared randomness rate and the communication rate in exact channel synthesis.

arXiv:2609.24120•Sep 21, 2026•0 citations

On Exact and ∞-Rényi Common Informations

Lei Yu, Vincent Y. F. Tan

Recently, two extensions of Wyner's common information-exact and Rényi common informations-were introduced respectively by Kumar, Li, and El Gamal (KLE), and the present authors. The class of common information problems involves determining the minimum rate of the common input to two independent processors needed to exactly or approximately generate a target joint distribution. For the exact common information problem, exact generation of the target distribution is required, while for Wyner's and α-Rényi common informations, the relative entropy and Rényi divergence with order α were respectively used to quantify the discrepancy between the synthesized and target distributions. The exact common information is larger than or equal to Wyner's common information. However, it was hitherto unknown whether the former is strictly larger than the latter for some joint distributions. In this paper, we first establish the equivalence between the exact and ∞-Rényi common informations, and then provide single-letter upper and lower bounds for these two quantities. For doubly symmetric binary sources, we show that the upper and lower bounds coincide, which implies that for such sources, the exact and ∞-Rényi common informations are completely characterized. Interestingly, we observe that for such sources, these two common informations are strictly larger than Wyner's. This answers an open problem posed by KLE. Furthermore, we extend Wyner's, ∞-Rényi, and exact common informations to sources with countably infinite or continuous alphabets, including Gaussian sources.

IEEE Transactions on Information Theory•Jan 29, 2020•23 citations

Broadcast Channel Synthesis from Shared Randomness

Malhar A. Managoli, Vinod M. Prabhakaran

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.

arXiv:2405.05211•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•2 citations
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 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.
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.
Recently, two extensions of Wyner's common information-exact and Rényi common informations-were introduced respectively by Kumar, Li, and El Gamal (KLE), and the present authors. The class of common information problems involves determining the minimum rate of the common input to two independent processors needed to exactly or approximately generate a target joint distribution. For the exact common information problem, exact generation of the target distribution is required, while for Wyner's and α-Rényi common informations, the relative entropy and Rényi divergence with order α were respectively used to quantify the discrepancy between the synthesized and target distributions. The exact common information is larger than or equal to Wyner's common information. However, it was hitherto unknown whether the former is strictly larger than the latter for some joint distributions. In this paper, we first establish the equivalence between the exact and ∞-Rényi common informations, and then provide single-letter upper and lower bounds for these two quantities. For doubly symmetric binary sources, we show that the upper and lower bounds coincide, which implies that for such sources, the exact and ∞-Rényi common informations are completely characterized. Interestingly, we observe that for such sources, these two common informations are strictly larger than Wyner's. This answers an open problem posed by KLE. Furthermore, we extend Wyner's, ∞-Rényi, and exact common informations to sources with countably infinite or continuous alphabets, including Gaussian sources.
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.