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

Exact Channel Simulation under Exponential Cost

Spencer Hill, Fady Alajaji, Tamás Linder

Published Sep 17, 2025• 0 citations
OpenAlex

Abstract

In this work, we generalize results in exact channel simulation to an exponential communication cost, specifically to Campbell’s average codeword length L(t) of order t [1], and to Rényi’s entropy. In exact channel simulation, given a source of shared randomness, a sender wishes to communicate a message to the receiver so they can generate a sample from the conditional distribution PY |X. We lower bound the Campbell cost of channel simulation using any sampling algorithm, showing that it grows approximately as It+1(X; Y), where Iα is an appropriately defined α-mutual information of order α. Using the Poisson functional representation of Li and El Gamal [2], we prove an upper bound on L(t) whose leading α-mutual information term has order within ϵ of the lower bound. Our results reduce to the bounds of Harsha et al. [3] as t → 0. We also provide numerical examples for the additive white Gaussian noise channel, demonstrating that the upper and lower bounds are typically within 5-10 bits of each other.

Related papers

Exact Sampling Under Campbell Cost via Rényi Channel Simulation Divergence

Yijun Fan, Aaron B. Wagner

We study the communication cost of exact sampling under Campbell's exponential coding criterion. Given a target distribution $P$ and a proposal distribution $Q$, the sender and receiver share i.i.d. $Q$-distributed samples, and the sender communicates an index so that the selected sample has distribution exactly $P$. We introduce a new information measure Rényi channel simulation divergence $R_α(P\Vert Q)$, a Rényi generalization of the channel simulation divergence. We then show that it lower bounds the Campbell cost of every exact sampler and is achievable, via a new layered sampling scheme, within an additive constant depending only on the Campbell parameter. This yields a tighter one-shot characterization than previous bounds based on Rényi divergences of different orders. For i.i.d. product distributions, under suitable non-degeneracy and moment conditions, we further show that the gap beyond the leading Rényi-divergence term is $\frac{1}{2}\log n+O(1)$.

arXiv:2610.15656•Oct 11, 2026•0 citations

Adaptive Greedy Rejection Sampling

Gergely Flamich, Lucas Theis

We consider channel simulation protocols between two communicating parties, Alice and Bob. First, Alice receives a target distribution Q, unknown to Bob. Then, she employs a shared coding distribution P to send the minimum amount of information to Bob so that he can simulate a single sample X ~ Q. For discrete distributions, Harsha et al. [1] developed a well-known channel simulation protocol – greedy rejection sampling (GRS) – with a bound of ${D_{{\text{KL}}}}\left[ {Q\left\| P \right.} \right] + 2\ln \left( {{D_{{\text{KL}}}}\left[ {Q\left\| P \right.} \right] + 1} \right) + \mathcal{O}\left( 1 \right)$ on the expected code-length of the protocol. In this paper, we extend the definition of GRS to general probability spaces and allow it to adapt its proposal distribution after each step. We call this new procedure Adaptive GRS (AGRS) and prove its correctness. Furthermore, we prove the surprising result that the expected runtime of GRS is exactly exp(D∞[Q║P]), where D∞[Q║P] denotes the Rényi ∞-divergence. We then apply AGRS to Gaussian channel simulation problems. We show that the expected runtime of GRS is infinite when averaged over target distributions and propose a solution that trades off a slight increase in the coding cost for a finite runtime. Finally, we describe a specific instance of AGRS for 1D Gaussian channels inspired by hybrid coding [2]. We conjecture and demonstrate empirically that the runtime of AGRS is $\mathcal{O}\left( {{D_{KL}}\left[ {Q\left\| P \right.} \right]} \right)$ in this case.

arXiv:2304.10407•IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2023•10 citations

Exponential evaluations in universal random privacy amplification

Masahito Hayashi

Abstract — We derive a new upper bound for Eve’s information in secret key generation from a common random number without communication. This bound improves on Bennett[7]’s bound based on the Rényi entropy of order 2 because the bound obtained here uses the Rényi entropy of order 1+s for s ∈ [0, 1]. This bound is applied to a wire-tap channel. Then, we derive an exponential upper bound for Eve’s information. Our exponent is compared with Hayashi[8]’s exponent. For the additive case, the bound obtained here is better. The result is applied to secret key agreement by public discussion. Index Terms — exponential rate, non-asymptotic setting, secret key agreement, universal hash function, wire-tap channel I.

•Apr 2, 2009•3 citations

Bounds on Covert Capacity With Sub-Exponential Random Slot Selection

Shi-Yuan Wang, Keerthi Suria Kumar Arumugam, Matthieu R. Bloch

We consider the problem of covert communication with random slot selection over binary-input Discrete Memoryless Channels (DMCs) and Additive White Gaussian Noise (AWGN) channels, in which a transmitter attempts to reliably communicate with a legitimate receiver while simultaneously maintaining covertness with respect to (w.r.t.) an eavesdropper. Covertness refers to the inability of the eavesdropper to distinguish the transmission of a message from the absence of communication, modeled by the transmission of a fixed channel input. Random slot selection refers to the transmitter’s ability to send a codeword in a time slot with known boundaries selected uniformly at random among a predetermined number of slots. Our main contribution is to develop bounds for the information-theoretic limit of communication in this model, called the covert capacity, when the number of time slots scales sub-exponentially with the codeword length. Our upper and lower bounds for the covert capacity are within a multiplicative factor of$\sqrt {2}$independent of the channel. This result partially fills a characterization gap between the covert capacity without random slot selection and the covert capacity with random selection among an exponential number of slots in the codeword length. Our key technical contributions consist of 1) a tight upper bound for the relative entropy characterizing the effect of random slot selection on the covertness constraint in our achievability proof; 2) a careful converse analysis to characterize the maximum allowable weight or power of codewords to meet the covertness constraint. Our results suggest that, unlike the case without random slot selection, the choice of covertness metric does not change the covert capacity in the presence of random slot selection.

arXiv:2409.07777•IEEE Transactions on Information Theory•Jul 16, 2025•1 citation

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

Exponential Decreasing Rate of Leaked Information in Universal Random Privacy Amplification

Masahito Hayashi

We derive a new upper bound for Eve's information in secret key generation from a common random number without communication. This bound improves on Bennett 's bound based on the Rényi entropy of order 2 because the bound obtained here uses the Rényi entropy of order 1+sfors∈ [0,1]. This bound is applied to a wire-tap channel. Then, we derive an exponential upper bound for Eve's information. Our exponent is compared with Hayashi 's exponent. For the additive case, the bound obtained here is better. The result is applied to secret key agreement by public discussion.

arXiv:0904.0308•IEEE Transactions on Information Theory•May 25, 2011•269 citations
In this work, we generalize results in exact channel simulation to an exponential communication cost, specifically to Campbell’s average codeword length L(t) of order t [1], and to Rényi’s entropy. In exact channel simulation, given a source of shared randomness, a sender wishes to communicate a message to the receiver so they can generate a sample from the conditional distribution PY |X. We lower bound the Campbell cost of channel simulation using any sampling algorithm, showing that it grows approximately as It+1(X; Y), where Iα is an appropriately defined α-mutual information of order α. Using the Poisson functional representation of Li and El Gamal [2], we prove an upper bound on L(t) whose leading α-mutual information term has order within ϵ of the lower bound. Our results reduce to the bounds of Harsha et al. [3] as t → 0. We also provide numerical examples for the additive white Gaussian noise channel, demonstrating that the upper and lower bounds are typically within 5-10 bits of each other.
We study the communication cost of exact sampling under Campbell's exponential coding criterion. Given a target distribution PPP and a proposal distribution QQQ, the sender and receiver share i.i.d. QQQ-distributed samples, and the sender communicates an index so that the selected sample has distribution exactly PPP. We introduce a new information measure Rényi channel simulation divergence Rα(P∥Q)R_α(P\Vert Q)Rα​(P∥Q), a Rényi generalization of the channel simulation divergence. We then show that it lower bounds the Campbell cost of every exact sampler and is achievable, via a new layered sampling scheme, within an additive constant depending only on the Campbell parameter. This yields a tighter one-shot characterization than previous bounds based on Rényi divergences of different orders. For i.i.d. product distributions, under suitable non-degeneracy and moment conditions, we further show that the gap beyond the leading Rényi-divergence term is 12log⁡n+O(1)\frac{1}{2}\log n+O(1)21​logn+O(1).
We consider channel simulation protocols between two communicating parties, Alice and Bob. First, Alice receives a target distribution Q, unknown to Bob. Then, she employs a shared coding distribution P to send the minimum amount of information to Bob so that he can simulate a single sample X ~ Q. For discrete distributions, Harsha et al. [1] developed a well-known channel simulation protocol – greedy rejection sampling (GRS) – with a bound of DKL[Q∥P]+2ln⁡(DKL[Q∥P]+1)+O(1){D_{{\text{KL}}}}\left[ {Q\left\| P \right.} \right] + 2\ln \left( {{D_{{\text{KL}}}}\left[ {Q\left\| P \right.} \right] + 1} \right) + \mathcal{O}\left( 1 \right)DKL​[Q∥P]+2ln(DKL​[Q∥P]+1)+O(1) on the expected code-length of the protocol. In this paper, we extend the definition of GRS to general probability spaces and allow it to adapt its proposal distribution after each step. We call this new procedure Adaptive GRS (AGRS) and prove its correctness. Furthermore, we prove the surprising result that the expected runtime of GRS is exactly exp(D∞[Q║P]), where D∞[Q║P] denotes the Rényi ∞-divergence. We then apply AGRS to Gaussian channel simulation problems. We show that the expected runtime of GRS is infinite when averaged over target distributions and propose a solution that trades off a slight increase in the coding cost for a finite runtime. Finally, we describe a specific instance of AGRS for 1D Gaussian channels inspired by hybrid coding [2]. We conjecture and demonstrate empirically that the runtime of AGRS is O(DKL[Q∥P])\mathcal{O}\left( {{D_{KL}}\left[ {Q\left\| P \right.} \right]} \right)O(DKL​[Q∥P]) in this case.
Abstract — We derive a new upper bound for Eve’s information in secret key generation from a common random number without communication. This bound improves on Bennett[7]’s bound based on the Rényi entropy of order 2 because the bound obtained here uses the Rényi entropy of order 1+s for s ∈ [0, 1]. This bound is applied to a wire-tap channel. Then, we derive an exponential upper bound for Eve’s information. Our exponent is compared with Hayashi[8]’s exponent. For the additive case, the bound obtained here is better. The result is applied to secret key agreement by public discussion. Index Terms — exponential rate, non-asymptotic setting, secret key agreement, universal hash function, wire-tap channel I.
We consider the problem of covert communication with random slot selection over binary-input Discrete Memoryless Channels (DMCs) and Additive White Gaussian Noise (AWGN) channels, in which a transmitter attempts to reliably communicate with a legitimate receiver while simultaneously maintaining covertness with respect to (w.r.t.) an eavesdropper. Covertness refers to the inability of the eavesdropper to distinguish the transmission of a message from the absence of communication, modeled by the transmission of a fixed channel input. Random slot selection refers to the transmitter’s ability to send a codeword in a time slot with known boundaries selected uniformly at random among a predetermined number of slots. Our main contribution is to develop bounds for the information-theoretic limit of communication in this model, called the covert capacity, when the number of time slots scales sub-exponentially with the codeword length. Our upper and lower bounds for the covert capacity are within a multiplicative factor of2\sqrt {2}2​independent of the channel. This result partially fills a characterization gap between the covert capacity without random slot selection and the covert capacity with random selection among an exponential number of slots in the codeword length. Our key technical contributions consist of 1) a tight upper bound for the relative entropy characterizing the effect of random slot selection on the covertness constraint in our achievability proof; 2) a careful converse analysis to characterize the maximum allowable weight or power of codewords to meet the covertness constraint. Our results suggest that, unlike the case without random slot selection, the choice of covertness metric does not change the covert capacity in the presence of random slot selection.
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 derive a new upper bound for Eve's information in secret key generation from a common random number without communication. This bound improves on Bennett 's bound based on the Rényi entropy of order 2 because the bound obtained here uses the Rényi entropy of order 1+sfors∈ [0,1]. This bound is applied to a wire-tap channel. Then, we derive an exponential upper bound for Eve's information. Our exponent is compared with Hayashi 's exponent. For the additive case, the bound obtained here is better. The result is applied to secret key agreement by public discussion.