Fast Channel Simulation via Error-Correcting Codes
Authors: Sharang M. Sriramu
Rochelle Barsz
Elizabeth Polito
Aaron B. Wagner
Venue: NeurIPS 2024 poster (2024)
Keywords: channel simulation
polar codes
linear codes
Error-correcting codes
quantization
data compression
DNN-based data compression
Primary area: probabilistic_methods

Abstract: We consider the design of practically-implementable schemes for the task of channel simulation. Existing methods do not scale with the 
number of simultaneous uses of the channel and are therefore unable to harness the amortization gains associated with simulating many uses of the channel at once. We show how techniques from the theory of error-correcting codes can be applied to achieve scalability and hence improved performance. As an exemplar, we focus on how polar codes can be used to efficiently simulate i.i.d. copies of a class of binary-output channels.

Fast Channel Simulation via Error-Correcting Codes
Sharang M. Sriramu School of ECE
Rochelle Barsz School of ECE Cornell University Ithaca, NY 14853 rsb359@cornell.
Elizabeth Polito
School of ECE
Coreell University Ithaca, NY 14853
Cornell University Ithaca, NY 14853
sms579@cornell.
emp234@cornell. edu
Aaron B. Wagner
School of ECE Cornell University Ithaca, NY 14853 wagnerccornell. edu
Abstract
We consider the design of paatically-implemmnnbbe schemes for the task of channel simulation. Existing methods do not scale with the number of simultaneous uses of the channel and are therefore unable to harness the amortization gains associated with simulating many uses of the channel at once. We show how techniques from the theory of error-correcting codes can be applied to achieve scalability and hence improved performance. As exemplar, focus on how polar codes can be used to efficiently simulate i.i.d. copies of a class of binary- output channels.
Introduction
Channel simulation refers the task in which Alice observes a realization of random variable X and sends a bit string to Bob. Bob, who shares common randomness with Alice, outputs a random variable Y using both the message and the common randomness. The goal is to minimize the length of the bit string subject to the constraint that Y should have a specified distribution Pyix (-(x). This problem can be viewed as a "soft" or "stochastic" generalization of quantization. As with quantization, Y has a digital representation (through Alice's 's message), and it can be viewed as degraded version of X. The difference is that here the degrading process is stochastic in general. In fact, the quantization problem is subsumed by taking the channel Pyxx to be deterministic.
This stochastic generalization of quantization arises in lossy compression of various types of sources including images |Flamich et al. 2020) Ballé et al. 2020). models (Havasi et al. 2018). and gra- dients (Shah al. 2022]. In these applications, X often represents vector latent variables, model weights, or even an image consisting of millions of pixels (Teis et al.) 2022]. The channel of interest therefore high dimensional, and it is usually independent across the dimensions. For conventional quantization, it has long been recognized that the optimum rate-distortion tradeoff more favorable in higher dimensions [Cover and Thomas 2006). trend that one expects to generalize to channel simulation. Indeed, let n - R, be the minimum number of bits required to generate y (Yi.... YY),, when X is i.i.d. and y conditionally i.i.d. given X". Thus R,, is the minimum number of bits per dimension when simulating the channel n times. The sequence n.R,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

can be shown to be subadditive and therefore satisfies (e.g., Liggett 1999 Thm. B22])
lim Rs inf Rn.
(1)
700000
It is known that R1 satisfies Li and El Gamal 2018
T(X;Y) R1 S T(X; Y) + log(T(X;Y) +1) 5,
(2)
where ((x; Y) refers to conventional Shannon mutual information. Applying this to i..dd (X", y") and using the fact that ((":)")) (Y) we have
nl (X; Y) S n R. S nI(X;Y) + log(nI - +,
which shows that as n + 30. R, approaches the lower bound YY) The challenge, for both quantization and channel simulation. that the complexity of schemes tends to grow exponentially in n. In fact, although many channel simulation schemes have been proposed [Harsha ct al. 2007]. (Li
and Hl Gamal 2018), (Flamich et al., 2022). FFlamich and Theis 2023]. [Flamich al. [024], none
have complexity that scales subexponentially in n. ignoring isolated examples for which R1 happens
to equal T(x; Y) Zamir and Feder
1992], [Agustsson and Theis 2020
Vector quantization has long been recognized to be the dual, in a precise sense, of channel cod- ing (Pradhan al. 2003]. In channel coding, the decoder maps an arbitrary point to an element of a finite set that is "close" in some channel-dependent sense. This is analogous to the role of the encoder in quantization. Likewise, the encoder in channel coding analogous to the decoder in quantization: both map bit strings to elements of said discrete set. Thus new techniques for channel coding can often be applied vector quantization [Goblick] 1963]. [Viterbi and Omura 1974] and
vice versa [Laroia et al. 1994).
The goal of this paper is demonstrate how ideas from coding theory can be applied to the channel simulation problem. We shall see that by adopting these techniques, we can develop schemes that significantly outperform state-of-the art methods, both in terms of their scalability and their rate performance. Specifically, we show how polar codes [Arikann 2009] can be applied to the simulation problem using a method called PolarSim. Polar codes make for good exemplar of this general proposal for five reasons. First, they have excellent channel coding performance, both theoretically [Mondelli et al. 2016) and practically (Egilmez et 2019]. Second, their complexity scales as log n. Third, they require no manual tuning. Fourth, they are simple to describe, requiring minimal background in coding theory. Finally, there exist highly optimized implementations of the encoding and decoding algorithms (e.g., [Phister, 2 ). Their limitation is that, in their basic form, they can only be applied symmetric binary-input channels (see (4) to follow). As we shall see, this means that PolarSim can only simulate symmetric binary-output channels. This class includes, for example, the binary symmetric channel, the (reverse) binary erasure channel, and channels of the form X - signum(X (X + 2), where X and Z are real-valued, independent random variables with symmetric distributions. Note that the input to the channel need not be binary and may even be continuous.
For these channels, we show both theoretically and experimentally that, by scaling up the dimension. the rate of PolarSim can be made to approach the mutual information lower bound / (X; Y) < Rr from (3). The superior scalability of PolarSim thus translates to a significant rate improvement over the state-of-ther thrt since those schemes are not able to harness the amortization gain associated with letting n grow. Although PolarSim is restricted to binary-output channels, it worth noting that there are currently no known schemes that simulate any nontrivial class of channels with even subexponential complexity in n. Also, for compression applications, a binary output alphabet not unreasonable. It should be emphasized that the binary-output restriction is particular to the basic form of polar codes, not error-correction methods in general. In the supplementary materials we discuss how different coding technique, trellis coded modulation, can be applied to closely simulate a Gaussian channel. See also the discussion in the Concluding Remarks section on non-binary polar codes.
One lesson from the coding theory literature, especially with the advent of modern coding theory in the 1990s [Richardson and Urbanke, 2008). is that it is advantageous to prioritize scalability with the dimension n over achieving optimal performance for particular n. The reason is that performance naturally improves with increasing (as in (1-3 above), and this improvement can overcome suboptimality at any given value of n. For sfate-of-the-art channel codes, the decoder typically does not implement the optimal (maximum likelihood) decision rule. Instead, it implements
2

---

scalable approximation to it. This design strategy of favoring scalability over optimality is now well established in coding theory and vector quantization, and our goal here is show how it can be profitably applied to channel simulation.
The rest of the paper is organized as follows. We provide the necessary background on polar codes in Section 2 Section 3 describes the PolarSim scheme, with Section 3.3 containing the theoretical result and Section 3.4 contains simulation results. Some concluding remarks are offered in Section 5
1.1 Terminology and Notation
We follow the standard convention of denoting the dimensionality of vectors by their superscript. We will also denote compound i.i.d. channels by superscripts: px" denotes n. i.i.d. copies of distribution p. The number of copies here is referred to as the block length or dimension of the channel. This is to be distinguished from the notation p which denotes n-fold self- Kroneckre product of a tensor F. All logarithms mentioned this paper are base 2. The binary entropy function
hB : [0, 2 + [0. 1] is defined as (p)p)) -p pogp (1 p) log(1 (1- p). We will also refer to its
inverse BB" [0, + [0, ]] defined such that h (hB(P) p.
2 Background
2.1 The Channel Simulation Problem
Consider joint probability measure PXY on the set X' x V. Alice receives a sequence of n symbols from the input alphabet X' drawn according to pi and encodes it into a binary string that she transmits to Bob. Upon receiving the message from Alice, Bob then decodes it to generate a sample from the channel Pý]x- The objective is to find coding schemes that minimize the average rate- i.e., the average amortized length of the bit string transmitted by Alice We refer to n as the block length or the dimension. We require that the set of strings that Alice can transmit to Bob to form a prefix-free set, meaning that no string in the set is a prefix of any other. Alice's message is thus self-terminating. and schemes for block length and n can be combined to obtain scheme for block length m by concatenation. If R. denotes the minimum average rate, i.e., the minimum average length of Alice's string over all schemes, normalized by n. then nR, is subadditive in n, as noted earlier.
xn
Both Alice and Bob are permitted to use randomized strategies and are assumed to share a source of common randomness. Under this assumption, Li and El Gamal [2018) prove the performance bounds (2) and 3 above (see also Harsha et al. [2007]. For large n, Sriramu and Wagner (2024) improve upon this result for i..dd discrete memory lessoryless channels, showing that the logarithmic redundancy term can be halved for some channels and eliminated for all others. While these schemes are nearly rate-optimal, their complexity scales exponentially in Other practical schemes have been proposed, although none have even subexponential scaling in n outside the small class of channels for which the lower bound in (3) is tight for all
2.2 Background on Polar Codes
Modern coding theory has focused on the search for codes whose rates approach the theoretical limit while having a low encoding and decoding complexity. Polar codes are among the crowning achievements of this search. In their basic form, they are accieiing linear codes for binary input channels Wx (+1) satisfying the following symmetry condition: there exists a bijection X + X' such that
and
(x W (1)))]1 for all a E X.
As a linear code, the encoding procedure for polar codes is defined by a generator matrix G,, that maps input L {0, 1)"H to the channel input Y Y = =U"G,, with all operations performed over F2. The generator matrix of size n = 2n can be constructed recursively from a kernel matrix F = [1 and the "bit-reversal" permutation matrix B,-seel see Arikan 2009). The generator matrix is then defined as G, = Fron The structure of the generator matrix allows for encoding in n log n time.
Decoding proceeds by sequentially guessing each bit of U in order. For this, one considers the subchannel U, + (U*-1, ))",. Specifically, given the realization of the output x" and the decoding
3

---

decisions for the prior bits i' one computes the likelihood ratio
- = 21-1) Pr(U. 1|X" - -r",
Pr(U, = 0|X" = xr,, --, 5:-1)
(5)
and selects Ü, accordingly. This decoding rule suboptimal but scalable in that the likelihood ratio can be computed in log steps using the recursive structure of G, [Arikan 2009]. resulting in decoding complexity of log n.
The suboptimality turns out to be acceptable because as n grows, the subchannels polarize, meaning that for most i the likelihood ratio (5) is close 0, oo with high probability. Equivalently, the mutual information [U;; X", U is close to zero one. Figure I iillustrates this phenomenon for binary symmetric channel (BSC) which is defined by X = Z, where Z Bernoulli(p) for some crossover probability E [0, 1].
the "clean" subchannels with mutual information close to 1 to send information bits. The inputs to the remaining noisy channels, called the frozen bits, are fixed ahead of time and known to both the encoder and decoder. The data rate is thus the fraction of subchannels that are clean, which can be shown to approach capacity [Arikan 2009].
For communication, the encoder
Implementing the code requires determining which indices correspond to the clean subchannels. This can done using the dimensionality reduction technique of Tal and Vardy [2013), by exploiting the recursive structure of the polar transform Zhang et al. 2014 Arikan 2009 or by Monte Carlo
simulation.
3 Simulating Binary Output Channels
Previously, we described polar codes for constructing channel codes for binary input channels. Based on the duality between channel coding and channel simulation, we will see that this naturally leads to scheme for simulating binary oulput channels.
We begin by describing a "toy scheme". This is not a rate-efficient scheme in its own right, but serves as foundation for PolarSim.
3.1 Toy Scheme for Binary Output Channel Simulation
Consider joint distribution Pxy where py is Bernoulli (t). Then, the following algorithm simulates Py|x exactly:
1. Use the common randomness to generate Z ~ Unif 1) and V = 1 (2 > +) at both the encoder and decoder.
2. At the encoder, having observed an input realization x, compute the output bit Y = = == V.
1 (Z > Pyjx (0[2)) and the correction bit A
3. Transmit A to the decoder after lossless compression.
4. Recover Y
@ V the decoder.
In Appendix A we show that the rate associated with repeated application of this scheme is upper bounded by he (1 - hg 1 (1- I(X; Y))). As can in Figure 2 this is highly suboptimal in general. However, we note that for the special case in which the mutual information is polarized, i.e., where Y) z 0 or I(X;Y)
1, the toy scheme is close to optimal.
This observation is crucial as it suggests a path forward: If we can transform a given channel simulation problem to the problem of simulating polarized channels, it can be solved rate-efficiently using the toy scheme. Polar codes provide us with the means to achieve such a transformation.
3.2 Channel Simulation using Polar Codes
As in the toy scheme, we shall consider a joint distribution pxy where py Bernoulli (t). We will additionally assume that pxly satisfies the symmetry condition described in (4). Let then examine

---

0.8
0.6
0.4
0.2
Bits
1000
2000
3000
4000
0
1000
2000
3000
4000
1.0
0.8
0.6
0.4
0.0
10000
20000
30000
10000
20000
30000
Index
Sorted Indices
Figure Channel polarization BSC with crossover probability 0.2 and black lengths n = 2 (top) and N 2 (bottom). The scatter plots on the left show the subchannel capacities [(U;; ""; -,"+1) for each index i. In the curves (m) the right. these indices are sorted in the increasing order of their subchannel capacities for better visualization. The area under these curves the mutual information lower bounds at their respective block length. The vertical dotted line marks the idcal polarized channel, i.c., the fraction of indices its right equal to the mutual information the channel. We see that the sorted subchannel capacity curve approaches this line as the block length is increased. Finally, we also plot the theoretical upper bound (sec (38) on the rate of our proposed scheme. PolarSim, for block lengths upper bound on the rate of PolarSim. The shaded area in between therefore upper bound the redundancy of PolarSim, which vanishes as n -> oo due to the polarization phenomenon.
2 and n 2 The area under these curves
0.8
0.6
Rate
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
T(X; Y)
Figure 2: The upper bound on the rate of the toy scheme described in section mutual information lower bound (m).
is plotted against the
5

---

the problem of simulating two independent realizations of the channel pr|x, X2 - Y Consider the following bijection applied to the output (X1.X))
U = Y1 + 2/2
U2 Y2
(6)
It is clear that simulating the original pair of i.idd channels X1 Y1 and X2 - Y2 is equivalent to simulating the transformed pair of channels (2) + U1 and (X1,X2g U1) + U2.
The mutual information of each of the original i.i.d. channels are equal to T(X; Y) However, the two transformed channels differ in terms of mutual information: T(X1, X2, U1: U2) > Y(X;Y) because
U2 is observed through two different channels. This necessitates that the other channel has lower mutual information: I X2; U1) < YY: Therefore, the linear transformation (6) we applied to the output had the effect of polarizing the target channel.
For block lengths that are larger powers of two, we can apply the transform inductively, resulting in the relationship we saw in section 2 t = Y"Gā'' Similar to the two- wwo-dimesiional (n 2) case, this transforms the original simulation problem X Y into the problem of simulating the subchannels X - (X." U1
+ U2 (X", Ur,,UU1U0 U2) - Uz...., (X" "",,U""1 Un. Arikan 2009) shows that these subchannels are polarized for large n: for each i, T(U,; X U Ri 0 or IU;; U)- 2 1. This allows us to simulate them using the toy algorithm described in the previous section.
Algorithms
and describe the complete scheme.
Algorithm 1: Encoder simulating a channel using polar codes.
Input Blook length
Random bit string =" Unif ((0, 1lm)
Probability table p" E 10, Source string x" E xm
Output::tringg b (0,1)* for = 1,...,71 do SoftPolarDec(z", 1²-1) then u, + else u, 2 > 1/2 then U; + 1 else 17 + 0 A; u4 + U; 6 + Compress ( ( )")
return b
Algorithm 2: Decoder for simulating channel using polar codes.
Input Blook length
Random bit string z" Unif ((0, 1[") Probability table n E [o, 1]"
Compressed offset string b
Dutput::imulater channel output y" {0,1)"
A" +- Decompress(b,,
for i 1....,W. do
2; > 1/2 then is <- else ii 5- < A + Uy y" PolarEnc(u"")
return y"
The encoder input P. refers to the subchannel parameter
P. h (H(U,("'1))))
This can be calculated offline using the techniques used to compute subchannel quality for communi-
cation described at the end of Section 2 The SoftPolarDec(u- x²") subroutine outputs
Pr(U, 0lu _
x x²)
(8)

---

which can be calculated with The PolarEnc(u") subroutine simply multiplies by the generator matrix in: y" w This can be implemented in O(n log by exploiting the recursive structure, as noted earlier. The Compress A", (²)) and Decompress(b,, p*) routines can be any prefix-free lossless compres- sor/decompressor pair that uses at most
n) complexity using a recursion given by Arikan 2009).
1
c+ Σ
+1(A, 0) log 1(A: log log 1/2 p-
(9)
1/2 + Pi
bits to send A", where e some constant independent of n and A Arithmetic coding (Rissanen [9766) is widely-used scheme that achieves this guarantee with 2.
This defines PolarSim for n that a power of two. An arbitrary n can be handled by partitioning (1.....7] n into subsets, each of which has cardinality that is power of two. One then applies PolarSim to each subset separately. Since the coding prefix-free, the encoder outputs can simply be concatenated together, as noted in Sec. 2
3.3 Theoretical Guarantees
If one uses linear complexity algorithm for Compress and Decompress, then the overall complexity of PolarSim is On log n) for both encoding an decoding. Using the fact that polar codes achieve capacity for channels satisfying the symmetry condition in (4, we show that PolarSi: is rate optimal in the large-n limit, making it currently the only scheme with subexponential complexity in with comparable guarantee.
Theorem 1. Consider joint distribution Pxy in which Y is binary and uniform and the reverse channel Y satisfies the symmetry condition in 44. Suppose Compress and Decompress achieve the guarantee in (
1. (Correctness:) Algorithmss 7 and 2 simulate the channel (x*(X|X) exactly: If Z is
i..dd Unif 1), and p; ht (HU,, ,"),, then the conditional probability that Algorithm 2 outputs y" given that I" is the input to Algorithm is
II Py)x(U))
(10)
2. (Optimality:) Algorithmss 7and? are asymptotically rate optimal:
lim 1 [[((b)] I(X;)),
(11)
where is the output of the encoder.
The proof is provided in Appendix D
3.4 Experimental Results
We run PolarSim on the reverse (Pyix) version of three channels: (1) the BSC with uniform input (2) the binary erasure channel, X Z Y, where Y is uniform over {-1, and Z is Bernouli(c). and (3) the binary Gaussian channel X = Y + Z, where Y is again uniform over {-1, and Z is (0,00² o²). Note that the reverse of the BSC with a uniform input is the BSC itself.
Fig. 3 and Fig. show the rate performance of these simulations. Even at a block length of 2 the performance is already close to the mutual information lower bound across all channels and rates. Performance improves with n as expected, with both the average rate and the variance in the rate decreasing.
We also compare our scheme to the state-of-ther scheme for channel simulation, Greedy Poisson Rejection Sampling (GPRS) [Flamich] 2024] (see Appendix for the implementation details). Fig, 5 shows that PolarSim significantly outperforms GPRS in terms of the communication rate, even when the latter is optimized for the channel at hand. In Table [] we can see that its computational efficiency is also significantly better, by several orders of magnitude. This is due the exponential computational complexity of GPRS in compared to the pseudolinear complexity of PolarSim.
7

---

0.4
0.2
0.0
1.00
0.50
0.00
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Rate
Figure 3: Rates achieved by PolarSim at different block lengths middle-right).
2 (leff).. n 2 (top-right and 2 (bottom-right) for different noise levels different channels, compared against the theoretical lower bound (X; Top: BSC, E (0, }). Middle: Gaussian for a E (0,3). Bottom: Erasure E (0, 1). The lines represent the median values, and the boundaries shaded regions represent the 5th thth percentile rates 200 simulation
0.0
Redundancy
0.1
0.0
0.1
6
7
8
10
11
12
13
14
log Tl
The redundancy PolarSim is plotted for certain channels (Top: BSC with p 0.05, Middle: Reverse binary Gaussian channel with a = 0.5, Bottom: Reverse hinary crasure channel with = 0.2) the block length varied. The plotted curve (m) the median redundancy over 200 simulations, with the boundaries of the shaded region showing the bootstrapped 95% confidence interval around the sample median. The redundancy is defined as the gap between the achieved rate the mutual information lower bound. comparison, the theoretical maximum redundancy of PFRL is also plotted for the respective channels (see
Figure 4:
3.. We see that for large block lengths, PolarSim has higher redundancy, which is consistent with known results from channel coding [Mondelli et al. 2016).

---

1.4
1.2
1.0
0.8
Rate
0.6
0.4
0.2
0.0
0.0
0.2
0.4
0.6
1.0
I();Y)
Figure 5: Comparison of schemes for BSC simulation: Average rates for PolarSim with M m 242 and
n = 2 compared against GPRS with n = and the theoretical lower bound [(X; Y) over 1000 simulation
runs.
p
PolarSim
GPRS
Median
p5
p95
Median
p5
p95
0.00
0.009
0.008
0.01
192.0
161.4
205.8
21333
0.25
0.009
0.008
0.01
246.1
180.7
415.7
27347
0.49
0,009
0.008
0.01
227.7
176.1
318.7
25305
Table 1: Execution time comparison between PolarSim and GPRS, for simulating BSC's with block length 22 The reported statistics computed 1000 trials for each value of the crossover probability p. GPRS cannot directly simulate such large block lengths. Therefore, GPRS runtimes are obtained by scaling up the runtime for n 8 blocks. This is justified by subadditivity (see (I). The column À computes the ratio between the medians of the two schemes. For our chosen block length, PolarSim performs over four orders of magnitude faster than GPRS.
Related Work
4.1 Performance Bounds
Arguably the first to consider the channel simulation problem was Wyner 1975]. who studied the problem without common randomness. The problem with common randomness was first introduced
in the context of quantum information theory literature by |ennettt et al. [2002] and Winter (2002). Harsha et al. [2007] proposed a greedy one-shot channel simulation algorithm that achieved
logarithmic rate redundancy with respect to the lower bound for discrete channels. Li and El Gamal (2018) showed similar achievability result that generalizes to more general channels using their strong Poisson functional representation lemma. Sriramu and Wagner 2024] showed via two-stage rejection sampling scheme that an even lower redundancy was achievable in the i.i.d. case. [i and Anantharam 2021 extended the Poisson representation to obtain a generalised method for deriving one-shot achicvability in different settings (see also Phan et al. 2024)) )
Practical Schemes
The achievability proof in Li and El Gamal (2018) inspired several practical schemes that exploit
properties of the Poisson process and perform well at short block lengths [Flamich et al.) 2022 Flamich 2024]. Similarly, the rejection sampler proposed by Harsha et al. [0077] has been generalized by Flamich al. [2224] to work for arbitrary probability spaces. None of these schemes exhibit subexpoential complexity with when applied to product channels, however. If one restricts attention

---

to n and unimodal distributions, then improved schemes are possible [Flamich et al., 2024 Hegazy and Li 2022]. although by their nature such schemes cannot harness the amortization gain associated with increasing
Chou et al. 2018 addresses the problem of total variation approximate channel simulation and proposes fixed rate scheme based on a soft covering argument that uses polar codes.
As noted in the introduction, the primary application of the channel simulation task is learned compression. [eii et al. [024] and et al. (2020) consider how vector quantization methods can be directly applied to the compression task without explicitly simulating channel. Although their methods do not simulate an i.i.d. channel, their use of ideas from error- correccing codes and vector quantization makes them the closest prior works to the present paper, along with Chou et al. [2018]
5 Concluding Remarks
PolarSim shows how polar codes can be used to simulate channels with favorable scalability in the dimension. By harnessing the attending amortization gain, the codes are able to realize significantly improved performance compared with existing schemes. Our focus has been on how the original form of polar codes can simulate symmetric, binary output channels. Subsequent extensions of polar codes [Saşoglu et al. 2009) could potentially be used to simulate arbitrary channels. This would be an interesting topic of future research.
The aim of the paper, however, not to show that polar codes are useful for simulation per se. Rather, seek make the larger point that ideas from the field of error-correcting codes are useful for the simulation problem. We have used polar codes as an exemplar, but one could potentially apply turbo codes (Berrou al. (T993). ), low-density parity-check codes LDPCs (Gallager (T962)
algebraic codes [Blahut] 2.003]. trellis-coded modulatioon/quantzaiii
(Taubman et al. 22022) ) sparse
superposition codes (Joseph and Barron (0122). or other codes (c.g.. Caire et al. (1988) ) instead.
The PolarSim method is not expected to generalize to these other families. Polar codes are linear, however, and one can transform them into a simulator for the BSC using a different approach that relies on linearity alone. This is discussed in the supplementary materials, where we find that this alternate scheme achieves comparable performance to PolarSim. This alternate approach is directly applicable to other linear codes such as LDPCs.
In learned compression applications, the channels of interest generally continuous. Error- correcting schemes that operate directly on continuous channels, such as trellis-coded modula- tion/quantization, are therefore of particular interest. To illustrate the potential of these codes, in the supplementary materials we show how trellis-coded quantization can be used to approximately simu- late Gaussian channel. The simulation is not exact, but practical applications, exact simulation may be unnecessary.
6 Acknowledgement
This research was supported by the US National Science Foundation under grant CCF-2306278 and by gift from Google. The authors wish to thank Lucas Theis and Jona Ballé for helpful discussions. They would also like to thank the anonymous reviewers for the feedback and suggestions they provided.
10

---

References
Gergely Flamich, Marton Havasi, and José Miguel Hernández-Lobato. Compressing images by encoding their latent representations with relative entropy coding. Advances in Neural Information Processing Systems, 33:16131-16141, 2020.
Johannes Ballé, Philip A Chou, David Minnen, Saurabh Singh, Nick Johnston, Eirikur Agustsson, Sung Jin Hwang, and George Toderici. Nonlinear transform coding. IEEE Journal of Selected Topics in Signal Processing, 15(2)3339333, 2020.
Marton Havasi, Robert Peharz, and José Miguel Hermández-Lobato. Minimal random code learning: Getting bits back from compressed model parameters. International Conference Learning Representations, 2018.
Abhin Shah, Wei-Ning Chen, Johannes Ballé, Peter Kairouz, and Lucas Theis, Optimal compression of locally differentially private mechanisms. arXiv preprint
2022.
Lucas Theis, Tim Salimans, Matthew D. Hoffman, and Fabian Mentzer. Lossy compression with Gaussian diffusion. arXiv preprint arXiv:2206.0888 2022.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, Hoboken, 2nd edition, 2006.
Thomas M. Liggett. Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Springer-Verlag. New York, 1999.
Cheuk Ting Li and Abbas El Gamal. Strong functional representation lemma and applications to coding theorems. IEEE Transactions on Information Theory, 64(1 (4(11))6967-6678 2018
Prahladh Harsha, Rahul Jain, David McAllester, and Jaikumar Radhakrishnan. The communica- tion complexity of correlation. In Twenty-Second Annual IEEE Conference Computational Complexity (CCC*07), pages 10-23. IEEE, 2007.
Gergely Flamich, Stratis Markou, and José Miguel Hemúndez--obato. Fast relative entropy coding with A coding. In International Conference on Machine Learning, pages 6548-6577. PMLR,
2022.
Gergely Flamich and Lucas Theis. Adaptive greedy rejection sampling. 2023 IEEE International Symposium on Information Theory (ISIT), pages 454 2023.
Gergely Flamich, Stratis Markou, and José Miguel Hernández-Lobatt Faster relative entropy coding with greedy rejection coding. Advances in Neural Informution Processing Systems, 36, 2024.
Ram Zamir and Meir Feder. On universal quantization by randomized uniform/latiice quantizers.
IEEE Transactions on Information Theory, 38(2):28-436, 1992.
Eirikur Agustsson and Lucas Theis. Universally quantized neural compression. Advances in Neural Information Processing Systems, 33: 12377-12376., 2020.
S.S. Pradhan, J. Chou, and K. Ramchandran. Duality between source coding and channel coding and its extension to the side information case. IEEE Transactions on Information Theory, 49(5): 1181- 2003. doi: 10.1 109//TT..003.8100000
Thomas John Goblick. Coding for a discrete information source with a distortion measure. PhD thesis, Massachusetts Institute of Technology, 1963.
A Viterbi and J Omura. Trellis encoding of memoryless discrete-time sources with a fidelity criterion. IEEE Transactions on Information Theory, 20(3):325-33) 1974.
Rajiv Laroia, Nariman Farvardin, and Steven A Tretter. On optimal shaping of multidimensional constellations. IEEE Transactions on Information Theory,
1994.
Erdal Arikan. Channel polarization: A method for constructing capacity-achieving codes for sym- metric binary-input memoryless channels. IEEE Trunsactions on Information Theory, 55(7): 3051-3073, 2009.

---

Marco Mondelli, S Hamed Hassani, and Rüdiger L Urbanke. Unified scaling of polar codes: Error exponent, scaling exponent, moderate deviations, and error floors. IEEE Transactions on Information Theory, 62( 2222)666666772 2016.
Zeynep B Kaykac Egilmez, Luping Xiang, Robert G Maunder, and Lajos Hanzo. The development. operation and performance of the 5g polar codes. IEEE Communications Surveys & Tutorials, 22 (1):96-122, 2019.
Henry Pfister. volar_intro http::pp//taaaoooo///////aaaaaaa intro 2023.
Tom Richardson and Ruediger Urbanke. Modern Coding Theory. Cambridge University Press, 2008.
Sharang M Sriramu and Aaron B Wagner. Optimal redundancy in exact channel synthesis. arXiv preprint arXhv:2401.16777, 2024.
Ido Tal and Alexander Vardy, How to construct polar codes. IEEE Transactions on Information Theory, 59(10)6552-6653 65882 2013, doi: 10.1 00.100//TT221132277666
Yingxian Zhang, Aijun Liu, Kegang Pan, Chao Gong, and Sixiang Yang. A practical construction method for polar codes. IEEE Communications Letters, 18(11):1871-187) 2014.
Jorma Rissanen. Generalized Kraft inequality and arithmetic coding. IBM Journal of research and development, 20(3):198 198-203, 1976.
Gergely Flamich. Greedy Poisson rejection sampling. Advances in Neural Information Processing Systems, 36, 2024.
A. Wyner. The common information of dependent random variables. IEEE Transactions Information Theory, 21(2):163-179 1975. doi: 10.1 19.1 1055346.
Charles H Bennett, Peter W Shor, John A Smolin, and Ashish V Thapliyal. Entanglementtaasistee capacity of a quantum channel and the reverse Shannon theorem, IEEE transactions on Information Theory, +8(10):2637-2655 2002.
Andreas Winter. Compression sources of probability distributions and density operators. arXiv preprint phant-ph/02081311, 2002.
Cheuk Ting and Venkat Anantharam. A unified framework for one-shot achievability via the Poisson matching lemma. IEEE Transactions on Information Theory, 67(5): 2651, 2021.
Buu Phan, Ashish Khisti, and Christos Louizos. Importance matching lemma for lossy compression with side information. In International Conference on Artificial Intelligence and Statistics, pages 1387-1395. PMLR, 2024.
Mahmoud Hegazy and Cheuk Ting Li. Randomized quantization with exact error distribution. In IEEE Information Theory Workshop (ITW), pages 350-355, 2022.
Rémi A Chou, Matthieu R Bloch, and Jörg Kliewer. Empirical and strong coordination via soft covering with polar codes. IEEE Transactions on Information Theory, 64(7):5087-5100, 2018.
Eric Lei, Hamed Hassani, and Shirin Saeedi Bidokhti. Approaching rate-distortion limits in neural compression with lattice transform coding. arXiv preprint arXiv:2403.07322, 2024.
Binglin Li, Mohammad Akbari, Jie Liang, and Yang Wang. Deep learning-based image compression with trellis coded quantization. In Data Compression Conference (DCC), pages 13-22, 2020.
Eren Şaşoğlu, Emre Telatar, and Erdal Arikan. Polarization for arbitrary discrete memoryless channels. In 2009 IEEE Information Theory Workshop, pages 144-148, 2009. doi: 109/1TW 2009.5351487.
Claude Berrou, Alain Glavieux, and Punya Thitimajshima. Near Shannon limit error-correcingg coding and decoding: Turboocodes.. In Proceedings of ICC*93-IEEF International Conference Communications, volume 2, pages 1064-1070. IEEE, 1993.
12

---

Robert Gallager. Low-density parity-checks codes. IRE Transactions on information theory, 8(1): 21-28, 1962.
Richard Blahut. Algebraic Codes for Data Transmission. Cambridge University Press, 2003.
David Taubman, Michael Marcellin, and Majid Rabbani. Jpeg2000: Image compression fundamentals, standards and practice. Journal of Electronic Imaging, 11(2):286-28) 2002.
Antony Joseph and Andrew R Barron. Least squares superposition codes of moderate dictionary size are reliable at rates up to capacity. IEEE Transactions on Information Theory, 58(5):2541-2557, 2012.
Giuseppe Caire, Giorgio Taricco, and Ezio Biglieri. Bit-interleaved coded modulation. 1EEE transactions on information theory, 44(3):927-946, 1998.
Andrew Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE transactions on Information Theory, 13(2):60-2699 1967.
13

---

A Rate of the Toy Scheme
The rate of this scheme is governed by the cost of compressing the correction bit A. We have
Pr(A = 1) E
Pr(4 = 1|x)]
(12)
E
min
Pyxx(ixx)
(13)
2
je(0,1)
1
E
min pr(x(i|x)
(14)
2
(iE(
1
min PY x (x11))
H(A) hB
E
(15)
2
(E(0,1)
Rearranging this, we can obtain
E
min pr(x = - -hg'(H(A)) (E(0,1)
(16)
Next, consider
1(x;Y)= = X
(17)
1 E hB
min pr (ilx))
(18)
jE(0,1)
2 1 hB
E
min Prix (
(19)
(E(U,1}
1
h (H(A))
1 hB
(20)
2
Rearranging this, finally obtain the required upper bound:
[ hg'(1 ((x:X))).
H(A)
< hB
(21)
B Trellis-Coded Quantization
The channel simulation scheme described in the the body of the paper is limited to binary-output channels. However, in many practical applications, we need to simulate channels with real-valued outputs. To demonstrate that the tools from coding theory are not limited to binary channels, we describe scheme that uses trelli coded quantization for approximately simulating AWGN channel for i.i.d. Gaussian source.
The encoding algorithm for trellis coded quantization was originally developed as an efficient decoding algorithm for a family of channel coding schemes called convolutional codes. We will directly describe the construction used in source coding as can be described in a self-contained manner.
A fixed-rate time-invariant trellis with i states S {81, 82,..., consists of a k x h binary transition matrix G where each row and each column have exactly two nonzero entries, a set of disjoint codebooks V (C,,C2,-... C2,-...Cmm with each containing 2 codewords from the source alphabet X, and a map T fl,..., k) x [I....,k] k} + V which assigns a codebook to each pair of states.
path of length n through the trellis consists a traversable sequence of states 8, (sta St.s..., St,, -iie, all sequences such that G(st, st,-,) = 1. For any sequence of codewords f", we will use the shorthand nn E 8; if 4" can be produced by the transitions of the path path-i.e.. f T(s st.) for all i.
In a data compression setting, the encoder, upon receiving a source sequence x", examines all traversable paths through the trellis to find codeword sequence o(x") that is closest to xt under the mean squared error distortion metrie:
((x")
arg min
||>:"" - 12
(22)
is travenaale
14

---

It then encodes this into bit-string by specifying the sequence of state transitions used and the codeword index in the associated codebook for each transition. Our chosen structure for the transition matrix G ensures that each transition can be encoded by one bit. Each codeword can be then indexed within the corresponding codebook using R bits, bringing the total communication rate R bits per symbol.
Although the search space for finding the best codeword grows exponentially in n, can be imple- mented efficiently using the Viterbi algorithm [Viterbi] 1967]. Here, at every stage k of our scheme, we keep track of the best paths terminating at every state s and their associated costs recursively:
J(s, k) min BES
J(8, k - 1)
min (ox - -x)²) and *ET(8,8)
(23)
((s, k) arg min J(, k))
(24)
The base case of the recursion is specified by the choice of the initial state Stg. which is typically
set to be $1. The initial costs are then set to be Js1 0) = O, and J 0) = oo for all $1 * s. The optimal state transition sequence and the corresponding codeword sequence o(x+) can be recovered using Ut.-).
To encode a sequence of length the Viterbi algorithm performs nm2 distance evaluations and 2nk comparisons thus, the computational cost grows only linearly in the block length making the algorithm highly scalable. Many practical data compression schemes use trellis codes due to this scalability, and because their performance terms of rate.
single-letter squared
B.1 Approximate AWGN Simulation Using TrellisCodeed Quantization
1. Let X ~ NO o²) be the input at the encoder, and f"(,, R) be a rate R trellis coded quantizer that obtains average distortion value of D. We a 256-state trellis with each state having exactly two branches leaving it, along with codebook of size 2t- which is
partitioned into 4 subsets, each of size 2 Each branch of the trellis is then associated
with one of the 4 subsets (See Figure 15 and Table 3.5 of Taubman et al. 2002 for full description of the mapping used for this assignment ).
The above Trellis is initialised with randomly generated codewords from standard normal and is subsequently trained using the Lloyd-Max algorithm.
Refer to Taubman et al. 2002 for a detailed description of the Trellis construction and training.
2. Using the common randomness, select a uniformly random rotation matrix at both the encoder and decoder.
3. At the encoder, compute the randomly rotated source X ILX" and the reconstruction X f(X", R). Transmit the reconstruction to the decoder by specifying the correspond- ing trellis path.
4. Compute the scaling factor - and the reconstruction y axmn
5. Finally, compute y = 1-" as the output of the channel simulation scheme. In figure σ we generate 100 independent realizations of X with 1000 and source power o² = 1. The scheme outlined above is then used to generate the corresponding Y realizations. The quantiles of the sample noise D | y² are plotted against the theoretical quantiles obtained by assuming | to be AWGN with noise power
Σ
1
we plot the rate of our approximate scheme (i.e. the rate of the trellis coded quantizer used) against the mutual information of the simulated channel. Bootstapped 95%ile confidence intervals for the mutual information are plotted to account for the error in estimating the noise power.
Figure 7
15

---

27
26
440
95
25
24
Sample Quantiles
90
23
85
380
22
300
75
Theoretical Quantiles
Figure 6: For trellis coded quantizers with rates R 1 (Left), R = 2 (Middle) and R 3 (Right), the quantiles for M 100 realizations of the sample noise D) ||Y X"I are plotted against the theoretical quantiles obtained from an AWGN with noise power E[D We use the sample mean estimate E[D].
Using a trellis with a fixed codebook limits the output alphabet to a finite set of real numbers. To simulate continuous channel, we introduce random orthogonal transformation, chosen by the common randomness, that is applied to the input before encoding. The decoder subsequently applies the inverse transformation to the reconstruction. This has the effect of randomizing the output symbols while retaining their proximity to the source on average.
We present the results of this scheme in Figures and We see that the distribution of the realizations of the simulated channel noise are fairly close to an AWGN with matching power, and that each of the operating rates of the trellis is very close to the mutual information of the simulated channel for that rate.
C Channel Simulation Using Arbitrary Linear Codes
Given any lattice A C Ra associated quantizer QA, and source realization X observed at the encoder, /Zamir and Feder 1992 provide a mechanism for simulating an additive noise channel whose noise distribution uniform over the decoding cell of the lattice,
(09) = (="h R Qx(=") 0*).
(25)
using dithered quantization: we generate 2 ~ Unif(Q (0*)) using the common randomness, and the encoder compute QA(X" + Z"), which transmitted the decoder. Then, according to Theorem in Zamir and Feder 1992]. computing
y QA(X" -7)
(26)
recovers a sample from the target distribution. analogous fact holds for linear codes over finite fields.
16

---

4
Rate
2
X
0
2
4
I(XY)
Figure 7: The rate of the trellis quantizer is plotted against the mutual information of the simulated channel. Bootstrapped 95% confidence intervals are plotted for the noise mean estimate.
C.1 Alternative Scheme for the BSC Simulation Using Polar codes
For a linear code to be capacity- achieving over a channel, its decoding cell must have a certain structure. For binary codes achieve the capacity of BSC (such as polar codes) their decoding cells must resemble Hamming balls. Thus applying the above procedure with polar code simulates additive noise channel in which the noise is approximately uniformly distributed over Hamming ball. Instead of using an additive dither to randomize the input to deterministic quantizer, we can randomly shift the codewords convenient for polar codes because shifting their cosets can be accomplished by randomizing the frozen bits, saving call to the quantization routine.
coset of the original lattice to have the same effect. This is especially
Suppose we seek to simulate n uses of BSC with crossover probability p. The number message bits is calculated as:
(1 hp()))
(27)
and the number of frozen bits is n m, which are generated using the common randomness. The simulation encoder takes the input bit string X" and the block of frozen bits. The simulation encoder runs the channel decoding algorithm with channel output X and the given frozen bits to obtain m message bits. These bits passed to the simulation decoder, which runs the channel encoder to produce y using the received message bits and the frozen bits. The role the encoder and decoder thus swapped compared to the communication task, was the case with PolarSim (see Fig. 8) The rate of this scheme is m/n.
This scheme does not result in exact simulation of n copies of the BSC,, however, in that X" ( y uniformly distributed over the cell rather than being i.i.d. Bernoullipp). This both because an i..dd Bernoull(p)) string is not constrained to single Hamming ball and because the cell of the polar code is not exactly a Hamming ball to begin with. Fig shows histogram of the number of bit-flips in this scheme compared with the target binomial distribution. We that the actual distribution of bit flips (top) has mean that is too high (because the cell not a true Hamming ball) and a variance that is too low (because the actual noise process is not constrained to single Hamming ball).
But we can upgrade this simulator one that achieves exact simulation using a pre- and post- correction process. The pre-correction is to adjust the parameter of the channel simulator to be P < which is chosen empirically to result in the correct (pn) number of bits being flipped on average. The post-correction scheme corrects for deviation in the variance and any remaining discrepancy in the mean and operates as follows. The encoder uses private randomness to generate realization of random variable N that is binomially distributed with parameters and p. It then runs the above
17

---

y
Y2
Xg
M4
Mgg
Sim.
Sim
Source
Encoder
Decoder
Channel Output
Bits
Y
Zp
Comm
Comm Encoder
yous
Decoder
Xp+1
Transmitted Bits
:
Ya
Frozen Bits
Mp+11
Rye
Figure Block diagram representation of BSC simulator based on polar codes. The role the encoder and decoder are swapped compared with conventional communication.
process, with pre-correction, and computes the number of bits flipped by the scheme. It then sends a correction message the decoder ensure that the actual number of bits flipped is exactly N. The correction message takes two forms, depending on whether one is operating in the high-rate or low-rate regime:
1. If m < 5: the encoder identifies the smallest L so that the first L bits of Y can be overwritten in such a way that the resulting y" string differs from X in exactly N positions. The encoder sends the decoder L using log n bits and then the L bits with which the decoder should overwrite the prefix of y
2. If 2 n. the encoder identifies a of bits that can be flipped result there being exactly N flipped bits overall. The encoder communicates to the decoder a binary string of length that contains I's and n L zeros. The encoder communicates using log bits. It then communicates the bit string using 2 + log (?) bits, which can be realized using arithmetic coding.
the decocder
By construction, the post-correction scheme ensures that the noise sequence 2 X Y has the correct distribution. The simulator is still not exact, however, because the distribution of 2" is exchangeable. This can be rectified by generating a random permutation of {l..... n). say II. from the common randomness and having the encoder apply II to X at the start and having the decoder apply II to Y the end. Note that an exchangeable distribution over binary strings with the property that the number of ones has a binomial distribution must be i.i.d. Bernoulli.
Note that the pre-correction part of the scheme is needed reduces the burden on the post-correction scheme. Also note that both the high-rate and low-rate schemes can be used for any value of m. We found empirically that the above division performed better than relying on either one alone. The performance of the corrected scheme is shown in (Fig. I0 which shows that the performance is similar PolarSim. The corrected scheme can never perform better than the uncorrected scheme, but the difference between the two vanishes as increases.
exact simulation; it only
The idea of fixing the number of bit flips using the common randomness is reminiscent of the two-stage channel simulation scheme Sriramu and Wagner (2024) and the layered randomized quantizer of Hegazy and Li 20022. ,, which are without loss of optimality in their respective setups. Note that the above scheme can be used to simulate a BSC using any linear code if one uses the dithered approach in 266 instead of relying frozen bits.
D Proof of Theorem
Theorem 1 Consider joint distribution Pxy in which Y is binary and uniform and the reverse channel P satisfies the symmetry condition 44. Suppose Compress and Decompress achieve the guarantee in 19.
18

---

150
100
Frequency
dh( (x",,, Y
12.
100
75
1900
1950
2000
2050
2100
d (*)
Figure Top: distribution the hamming distance, d (X", (x) Σ Y, between input binary string X and the output Y produced by the uncorrected polar simulator. Bottom: The target distribution, with
each Z. Bern(p) i..d.
0.5
0.4
p
0.2
0.1
0.0
Rate
Figure 10: BSC simulation using polar code simulator with post-correction. The median post-correction rate (m) plotted along with the uncorrected rate (m) and the mutual information lower bound (m). The boundaries of the shaded show the maximum and minimum rate for the corrected scheme over five simulation runs.
19

---

1. (Correctness:) Algorithms I and 2 simulate the channel p exactly: If z" is i.i.d. Unif 11. and p. hB (H(U,)U""). ,),),, then the conditional probability that Algorithm 2 outputs y" given that x" the input to Algorithm
II Prix(v)
(28)
2. (Optimality:) Algorithms 7 and 2 are asymptotically rate optimal:
lim [[((() - (X; n
(29)
where is the output of the encoder.
Proof. Suppose is power of two, and consider the following joint distribution between Y"):
Pr(U" = = y ," x²)) (x,)
II Prx Prxx(xla)))(""""""""""))))"))""1
= =-
(30)
;=1
1 G" II (x)l())) 2
(31)
Given the input X", the U string generated by the encoder has distribution p by construction, since Costtolaaree((rr u²=1, ,xlr) computes Pr(U: - x = x² U,- u w² under the distribution 13)-3111 Due to the lossless nature of the compression, A is recovered exactly at the decoder. Since V is common to the two terminals, U is thus recovered exactly by the decoder. Then setting Y U G results in (XX", y") having the joint distribution px* as desired. This establishes the correctness of the algorithm for n that is a power of two. Correctness of the algorithm for any n immediately follows.
Turning to optimality, again suppose n is power of two. For the sequence A we have
Pr(A, = 1) = Σ a--
Pui-ixx (u'-1, xx)) min Prr(U; 1 i-1 X = =x"), (32)
Pr(U, 0 = un 1,_ = x²))
(33)
1
Σ Poi (xx-(u") 22")h"" (H(U,)UU* " -²' = (34)
2
1
<
N (H(U)UU-1
(35)
2
2 D..
(36)
where the inequality follows by the convexity of h ( Thus the average rate may be bounded
1
F(((b)]
Pr(A: =o)log
+PrAA 0) log
(37)
n
1/2 pr
1/2 + P:
1
c
hB
(38)
2
We bound this quantity using the polarization property. Fix 8 0. By Arikan 2009 for all sufficiently large n there is A,, of "noisy" indices such that
W
> - T(X;Y) - 5
(39)
h1 p.) < 5 for all i E N,,-
(40)
20

---

The rate is thus upper bounded by
B[((b)]
72
Nn
Σ hB hB -.))
c
(41)
iEN
11 [a
8 8.
(42)
71
n
(X;; Y) 25
(43)
n
we R2 E[e(b]]/n denote the minimum rate of PolarSim at block length n (minimized over all partitions if it is not power of two), then n.,, is itself subadditive. As increases through powers of two, from (3 we have
Rn I(XY)).
(44)
and thus
inf R. - I(X;))
(45)
The result then follows by subadditivity (cf.
E GPRS Implementation Details
We implement Algorithm 3 from Flamich [2024] The proposal distribution P is chosen to be i.i.d. Bernoulli(1 /2) with n = 8. Given the input X x", the target distribution Q(y") is chosen to
be II. (yil(y)) where p ranges over (0, 1/2). The stretch function derived using the definitions provided in [Flamich 2023]:
log h - n (log(1 - p) + 1
wr(h)= = F
log p - log(1 - p) .B,
log h - n n(log(1 p)) 1)
w (h) F
log p - log(1 - p) 11,P)
and
h
1
(h))
wQ((1) ()) dn,
where n2,,,,,)) is the CDF of a Binomial(n,,) random variable. This stretch function was evaluated numerically for each input.
The algorithm outputs positive integer n, which is entropy coded using the Zeta distribution in [Flamich 2023, (151)). The number of bits divided by n obtain the rate. For each p on grid in (0, )) we run the simulation 200 times and plot the average rate obtained against the channel mutual information (p)).
We now make use of the fact that the selection rule employed by the algorithm needs be evaluated for each point in the output sample space only once - if the first occurrence of an output sequence in the randomly generated codebook rejected, all its subsequent occurrences are also rejected. This simplification helps speed up the execution significantly and also reduces the rate as repetitions need not be indexed.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The paper shows how ideas from error-correcting codes can be applied to the channel simulation problem, resulting in significantly improved performance both rate and computational complexity. Both the strengths and limitations of approach are noted in the abstract and the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Our main scheme can perform nearly rate-optimal channel simulation highly efficiently, but it is restricted to symmetric binary output channels. We make this clear even in the abstract. Our other scheme, using Trellis Coded Quantization, does not guarantee exact simulations. We make it clear that it is an approximate simulator in our description.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specifiiattio, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
22

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Theorem is stated with all necessary assumptions and has complete proof in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We describe algorithm and experimental setup in detail, and also include code as part of our supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
23

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We include code as part of supplementary material with instructions on how to run it.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/ mublic/guidess hogoll/cguiiees//odddellaassssso Cowdeeauuiisiiioooooioooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips. http/uullcggguucce http///ooeSuuiiissseeeeeee ssionPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Our algorithm description and the descriptions of our results are detailed enough to be reproducible. One of the virtues of the PolarSim is that there are no hyperpa- rameters to choose.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
The main plots that show the performance PolarSim and the post-correction scheme include error bars. Error bars were not included for the competitor schemes, PFRL and GPRS, due to their computational complexity. As noted in the paper, GPRS does not even consistently run to completion in reasonable time for some parameter values.
Justification:

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2- 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative етгог rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: It is noted the paper that all experiments were run on a consumer-gren grade CPU. It is also noted that PolarSim for 1024 takes less than 0.1 seconds per run. The context makes clear that the runtime for other experiments and channels are similar.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: //tee:/nneuiippe hcc/ppbllc//thhhccideee.....
Answer: [Yes]
Justification: All authors received prevailing wages course credit for their contributions to the paper. The paper is methodological and does not involve any datasets or human subjects.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
25

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This paper presents foundational research that is not expected directly lead to societal impacts. It could lead to improved compression schemes for various types of data, which would certainly be positive societal impact. This impact is implicit in the introduction.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not involve datasets of any kind. All experiments were run on synthetically generated data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
26

---

Justification: Other than our own code, we used Dr. Henry Pfister's s polar code imple- mentation pettps//githie
con//hearypffster/polla.a intro) on GitHub which is available under the "GNU Affero General Public License v3.0" license that places no restric- tions on usage. In our code, we have clearly mentioned which parts are derived from his code.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, pwpprssitthhaeeeo thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- se-packagdd, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes)
Justification: We provide the code we used to run our experiments along with instructions how run it.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Because the research presented in this paper involved neither crowdsourcing nor human study participants, this criteria not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
27

---

15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Because the research presented in this paper involved neither crowdsourcing nor human study participants, this criteria is not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
28


Reviews:
[{"review_id": "iLVan98HXz", "reviewer": "Reviewer_y5AJ", "summary": "The paper studies the channel simulation problem, whose goal is to minimize the number of transmitted bits so that the decoder can generate an output according to a target distribution given the encoder’s input. The paper proposes a channel simulation method, called PolarSim, based on polar codes. The rate of PolarSim approaches the mutual information lower bound by scaling up the block length, as theoretically proven and demonstrated by experiments.", "questions": "- Could the authors repeat their contributions in Conclusions so the contributions are clearer?\n- Please see Weaknesses for a few more questions.", "limitations": "The authors have explicitly addressed the limitations of their method.", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1.\tThe authors propose a novel method for channel simulation.\n2.\tThe paper is technically sound (to the best of my knowledge) and well-written.\n3.\tThe performance of the proposed method is impressive: The experiment results demonstrate that the proposed method achieves a rate approaching the theoretical bound, outperforming a quiet recent method.", "weaknesses": "1.\tThe smallest $n$ used in the experiments in the paper is $1024$. How would PolarSim perform for smaller $n$? Could the authors provide some figures in the supplementary material or at least comment on this?\n2.\tIn Figure 3, the authors mention that “Data for GRPS is only plotted for parameters where the algorithm consistently terminates in a reasonable amount of time.” It is unclear what the authors mean by “a reasonable amount of time.” Can the authors be more explicit about what they mean here? \n\nMinor comments and typos:\n\n1.\tThe figures would be easier to read if the colors were included in a legend within the plot.\n2.\tLine 55: Seems like “means that” should be “this means that.”\n3.\tIn line 118, I would suggest the authors to define the $F_2$ notation.\n4.\tLine 124: “likeihood” should be “likelihood.”\n5.\tLine 125: “thatl” should be “that.”\n6.\tLine 227: “)” is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging assessment of our work and for the comments and feedback you have provided. We have addressed specific comments and questions below.\n\n> The smallest used in the experiments in the paper is 1024. How would $\\mathtt{PolarSim}$ perform for smaller $n$? Could the authors provide some figures in the supplementary material or at least comment on this? \n\nIn our rebuttal PDF, we have provided a plot of the redundancy (meaning the rate minus the mutual information) versus $n$ for the $\\mathsf{BSC}, \\mathsf{BEC}$ and the $\\mathsf{AWGN}$ (Please refer to Figure 1. of the attached PDF). There we see that the $\\mathtt{PolarSim}$ scheme performs well even for small values of $n$. For comparison, we also plot the achievable rate from [Eq (1),1] (i.e. the upper bound), labeled in the plots as \"PFR UB\". We will include this in the camera-ready version of our paper, likely in the appendix.  \n\n> In Figure 3, the authors mention that “Data for GRPS is only plotted for parameters where the algorithm consistently terminates in a reasonable amount of time.” It is unclear what the authors mean by “a reasonable amount of time.” Can the authors be more explicit about what they mean here? \n\nWe were facing issues with getting the GPRS algorithm to terminate in high mutual information regimes during our experiments. However, we have followed the suggestions of reviewer w9ei to speed up the implementation of the GPRS algorithm and as a result, this issue is no longer a concern. We have presented the updated plot for Figure 3 (Please refer to Figure 2 in the attached PDF) which we will include in the camera-ready version of the paper.\n\n> Could the authors repeat their contributions in Conclusions so the contributions are clearer? \n\nThank you for this suggestion. We will take this into consideration when preparing the camera-ready version.\n\n> The figures would be easier to read if the colors were included in a legend within the plot. \n\nOur concern here was potentially overcrowding our plots. That said, we will try our best to make the suggested change work and include it in the camera-ready version.\n\nWe also thank you for pointing out certain errors and typos in our manuscript. We will be sure to incorporate these changes in our camera-ready version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cWAhRsxcN5", "reviewer": "Reviewer_6bFv", "summary": "This paper considers the scalability problem in the channel simulation. Channel coding, specifically polar coding, is introduced to improve the performance of channel simulation. The topic is interesting and the work is valuable.", "questions": "What is the meaning of the performance? \n\nHow to justify \"fast\" in the title?", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper uses error correction codes to improve the channel simulation with significant results.", "weaknesses": "The paper stresses \"fast\" in the title, but the corresponding justification or even a statement is missing in the main body of the paper. Some notations are not well defined. For example, what is the meaning of performance? It seems to be the rate, but it also seems to be speed (according to the title of this paper). \n\nA table is needed to compare the results with the other works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and comments. We have addressed specific comments and questions below. \n\n> The paper stresses ``fast'' in the title, but the corresponding justification or even a statement is missing in the main body of the paper. Some notations are not well defined. For example, what is the meaning of performance? It seems to be the rate, but it also seems to be speed (according to the title of this paper). \n\n> What is the meaning of the performance? \n\n> How to justify \"fast'' in the title? \n\nWe are interested in both (data) rate and (execution) speed, and, per (1) and (3) in the introduction, the two are coupled: a faster algorithm allows one to handle larger $n$, which improves the rate. \"Performance'' refers to the rate $R_n$ defined in the introduction, i.e., the average number of bits transmitted divided by the number of times the channel is being simulated.  \n\nWe felt that the term \"fast'' in the title was self-explanatory given that $\\mathtt{PolarSim}$ has $n \\log n$ complexity while (quoting from the paper) \"there are currently no known schemes that simulate any nontrivial class of channels with even subexponential complexity in $n$.\"\n\nThe speed of the scheme is what enables the improved rates that we observe in Figure. 3 (See Figure 2 of attached PDF for updated version)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Anqqx5Uuok", "reviewer": "Reviewer_Y8UR", "summary": "The manuscript considers the design of algorithms for channel simulation. This topic has been extensively explored in the information theory literature, under various names including 'Reverse Shannon Theorems', 'Channel Synthesis', and 'Channel Simulation'.\n\nThe primary concern is that the problem formulation, proposed solution, and underlying applications do not align with the core focus areas of this conference, making it more appropriate for information theory and theoretical computer science venues. Additionally, the writing and presentation require significant improvements. The problem formulation is not rigorously provided, and many of the statements and proofs are incomplete and inaccurate. The proposed approach lacks significant novelty. Furthermore, the scope is restricted to the synthesis of symmetric binary-input channels.", "questions": "- In Section III, the simulation of the reverse channel $P_{X|Y}$ is described in detail, and it is stated that the scheme is used to simulate the actual channel $P_{Y|X}$ without further explanation. Please explain the simulation procedure for the direct channel. \n- Please explain why the paper focuses on polar codes as opposed to other linear codes, given the comparatively high decoding complexity of polar codes. The alternative approach, which is applicable to other linear codes is only discussed in the appendix. How do the approaches compare and why is preference given to the one utilizing polar codes in this work?", "limitations": "As mentioned in the manuscript, a major limitation of the approach utilizing polar codes is the restriction to binary-input symmetric channels.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The channel simulation problem is of significant interest in the information theory community both in the classical and quantum settings.", "weaknesses": "- The problem formulation, proposed solution, and underlying applications do not align with the core focus areas of this conference, making it more appropriate for information theory and theoretical computer science venues. \n- The IID assumption on $X^n$ and $Y^n$, and the fact that only simulation of symmetric channels with binary-input is considered in the main body of the manuscript significantly limits the scope and applicability of the proposed algorithms.\n- It is not clear why the main focus of the paper is on polar codes. As mentioned in the appendices, the ideas presented in the paper (which have roots in source coding literature) are applicable to linear codes in general. The authors provide examples of Trellis codes and general linear codes and lattices in the appendices, whereas a significant portion of the paper is focused on discussing the properties of polar codes.  \n- Common randomness is used to generate uniform variables $Z_i$ which are then used in the simulation protocol. It is not explained how the uniformly distributed $Z_i$ are produced. For instance, if the randomness is communicated through a discrete noiseless channel as in [1], or is available as a binary string [2], then the users cannot produce completely uniform $Z_i$ with limited computational complexity, which makes exact channel simulation using the proposed protocol impossible. This is not an issue in evaluating the fundamental limits of channel simulation as in [1,2] since computational complexity is not the focus of those works, and $Z_i$ can be made as close to uniform as necessary. However, in this work, which considers efficiency and algorithm design, the computational complexity of producing $Z_i$ must be discussed, and the model for common randomness available to the users be described in more detail. That is, given a fixed n, how close does $Z_i$ need to be to a uniform variable, and what is the complexity of producing such $Z_i$ from a common random string?\n- Section III is not well-organized. The ideas are presented loosely and without formal introduction of the underlying concepts. The simulation of the reverse channel P_X|Y is described in detail, and it is stated that the scheme is used to simulate the actual channel $P_{Y|X}$ without further explanation. It is not clear why the description of the simulation protocol for $P_{Y|X}$ is not provided directly instead. \n\nMinor Comments:\n\nP.3 Line 99 -> blocklength m+n\n\nEquations (21) and (22) -> $Z_i$ should be $Z_1$ and $Z_2$, respectively. \n\n\n[1] Cuff, Paul. \"Communication requirements for generating correlated random variables.\" 2008 IEEE International Symposium on Information Theory. IEEE, 2008.\n\n[2]  Li, Cheuk Ting, and Abbas El Gamal. \"Strong functional representation lemma and applications to coding theorems.\" IEEE Transactions on Information Theory 64.11 (2018): 6967-6978.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We address your comments and questions below:\n\n> ... This topic has been extensively explored in the information theory literature ... \n\nWe disagree with this description. The information theory literature on this problem has predominantly focused on fundamental limits (i.e. theoretically achievable rates) without regard to computational complexity. Practically implementable schemes have mostly emerged from ML literature. See, e.g. [2-8].\n\n> ... the problem formulation, proposed solution, and underlying applications do not align with the core focus areas of this conference ...\n\nAgain we disagree: \n* The *problem formulation* is drawn directly from the above papers\n* The *proposed solution* is more of interest to the ML community because it proposes a fast, implementable scheme\n* The *applications* mentioned in the second paragraph of the introduction are all drawn from machine learning, with citations to papers in ML venues.\n\nWe are not aware of any work on channel simulation in the theoretical computer science community outside of [9], which is a decade old and focuses on fundamental limits, not practical schemes.\n> The problem formulation is not rigorously provided\n\nWe feel the problem formulation in Section 2.1 is comparably rigorous to various papers in the ML literature on this exact problem, such as [3,4,7]\n\nIt also matches that given in a more explicit form in many papers, e.g., [Section III, 10]; we can include such a formulation in the camera-ready version.\n> ... many of the statements and proofs are incomplete and inaccurate.\n\nThere is only one short proof in the paper (Theorem 1 in Appendix C), which in our estimation, is entirely rigorous and correct. We would appreciate it if the reviewer could substantiate this comment by noting specific assertions that are incomplete or inaccurate.\n> The proposed approach lacks significant novelty.\n\nWe view the use of error-correcting codes to achieve exact channel simulation as new.  Prior attempts have taken the form of hand-crafted solutions for small $n$ or variations on information-theoretic schemes --- completely different from PolarSim. We would appreciate it if the reviewer could substantiate this comment by indicating prior works with significant overlap.\n> ... restricted to the synthesis of symmetric binary-input channels\n\nThe channel must be binary output, not binary input. Otherwise, we agree that this is a limitation of the paper. But, we note that\n1. No existing scheme can achieve subexponential complexity for any nontrivial class of channels.\n2. Other coding schemes, including variations of polar codes, can handle nonbinary channels. In particular, see Appendix A for a scheme that simulates a continuous channel.\n3. For compression applications, binary-output channels are not unreasonable. Indeed, various papers have considered VAE-type architectures with discrete latents, including [11-13].\n    \nIn channel coding, no one code works optimally for all channels; different channels require different designs. It is natural to expect this to hold for channel simulation as well. Also, some existing schemes can only simulate a restricted class of channels [6].\n\n> The IID assumption ...\n\nAs noted in the introduction, several applications of interest require the simulation of an i.i.d. channel with sizable $n$. Arguably one of the limitations of prior schemes is that they seek to simulate i.i.d. channels but fail to capitalize on the structure that this assumption entails. Far from being a weakness, we view one of the contributions of the paper as pointing out that an i.i.d. channel assumption is both reasonable and valuable. \n\n> Please explain why the paper focuses on polar codes ...\n\nThe focus on polar codes is made clear in the introduction of the paper:\n\n\"First, they [polar codes] have excellent channel coding performance,\nboth theoretically (Mondelli et al. [2016]) and in practice (Egilmez et al. [2019]). Second, their complexity scales as $n \\log n$. Third, they require no manual tuning. Fourth, they are simple to describe, requiring minimal background in coding theory.\"\n\nPolarSim relies on certain unique properties of polar codes; it does not extend to arbitrary linear codes.  \n\nThe schemes presented in the appendix have limitations: The dither-based approach in Appendix B can only simulate the BSC (because the input and output alphabets must be the same), and the trellis-based approximate AWGN simulator has no theoretical guarantees.\n \nAlso, note that the decoding complexity of polar codes is $n \\log n$. It is low, not high.\n\n> Common randomness ...\n\nThe availability of infinite common randomness is the prevailing assumption in the ML literature on this problem. Determining the degree of \"exactness\" needed and the adequacy of pseudo-randomness are important and difficult problems, but they transcend this work and merit a separate paper.\n\n> Section III ...\n\nThe beginning of Section 3 is focused on providing intuition for the main algorithm and hence written in an expository style while still preserving mathematical correctness. For a formal description, one should rely on Algorithms 1 and 2, Theorem 1, and the experimental results.\n\n> The simulation of the reverse channel ...\n\nThe inherent duality between channel coding and channel simulation means that the way to use channel codes for simulation is to swap the roles of the encoder and the decoder, i.e., the channel coding decoder becomes the channel simulation encoder and vice versa. Thus, using the channel code for a channel $p_{Y|X}$, we can simulate the reverse channel $p_{X|Y}$.\n\nGiven its fundamental nature, we chose not to hide this swap in our exposition. However, given that it has caused some confusion, in the final version we will develop the PolarSim scheme without highlighting this. Thank you for bringing this to our attention.\n\nWe also thank you for pointing out typos and errors; we will correct them in the final draft.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OR5bn57Wob", "reviewer": "Reviewer_w9ei", "summary": "Inspired by the duality between source and channel coding, the authors use polar codes to develop a channel simulation algorithm for binary output channels. Notably, the authors' scheme scales as $O(n \\log n)$ where $n$ is the channel dimension, providing an example of a channel simulation algorithm whose runtime scales sub-exponentially in $n$ that doesn't rely on dithered quantization. The authors conduct some toy experiments to showcase the behaviour of their algorithm.", "questions": "Not so much a question but a suggestion: In Figure 3, the authors note that \"Data for GRPS is only plotted for parameters where the algorithm consistently terminates in a reasonable amount of time.\" If I understand correctly, the authors are simulating a vector of 8 iid Bernoulli channels. Since, in this case, the sample space is finite and has few elements (only 256), the implementations of PFR and GPRS can be simplified. To see this, note that if we draw the same sample twice, the one with the later arrival time will never be accepted. This motivates a simple strategy: simulate the arrival time for each element of the sample space and perform a brute-force search to find the element that fulfils the acceptance criterion. In the case of PFR, this is equivalent to just performing the Gumbel-max trick. It would be good if the authors could improve their implementation using the above solution (or otherwise) to provide a more complete comparison of the methods in Figure 3.", "limitations": "While the authors clearly state that polarization occurs for large $n$, providing a plot of this phenomenon would be valuable. For a fixed amount of mutual information (e.g., uniformly distributed across the dimensions), the authors could include a plot of the rate of PolarSim versus the problem dimensionality.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Overall, I am very excited about this paper. The general idea of exploiting the duality between source and channel coding to develop fast channel simulation algorithms could significantly impact the field and thus have far-reaching implications for neural compression. \n\nThe authors' concrete scheme is relatively simple, leaving little doubt about its correctness and efficiency. However, they do back things up with appropriate theoretical results. I have checked the proofs of the statements and can confirm that they are correct.\n\nFinally, the authors provide further discussion in Appendices A and B on possible future directions / concrete examples of channel codes that could be used to develop new channel simulation algorithms.", "weaknesses": "I should note that while I have expertise with channel simulation algorithms and have some basic familiarity with channel codes, I am not an expert in the latter.\n\nGiven the above, I found the paper's biggest high-level weakness to be its non-replicability, though most of it should be easily fixable. The biggest issue is that the description of the experimental setup for the comparison study between PolarSim, GPRS and PFR is missing, which means that Figure 3 and the last paragraph in the section are not interpretable. While the first set of experiments in Section 3.2 is better explained, the authors should also include the analytic form of the mutual information (the green curves in Figure 2) to make the results more interpretable. Similarly, the contents of Appendix A are quite high-level, with most of the experimental details missing; hence, again, Figure 4 is not interpretable. These problems should be easily fixable by providing the essential details of the experiments in the main text and an additional section in the appendix that describes the precise setup; I am happy to increase my score once the authors address this. I saw that the authors provided their code in the supplementary material; hence, the paper's contents are technically reproducible. Still, ideally, the paper should have sufficient detail so that someone can reproduce the experiments without the authors' code.\n\nThe second weakness of the paper is that it is closer to a position paper both in terms of content and impact. As the authors explain, \"The aim of the paper, however, is not to show that polar codes are useful for simulation per se. Rather, we seek to make the larger point that ideas from the field of error-correcting codes are useful for the simulation problem.\" Now, I believe the paper should be accepted just based on the strength of the idea (given that the authors address my first concern). However, the paper could have been significantly stronger if the authors considered some practical applications of their scheme and carried out more extensive experiments to demonstrate its usefulness.\n\n## Typos & Miscellaneous:\n - line 89: should be $h_B^{-1}(h_B(p)) =  p$\n - line 99: \"$m + n$y\" instead of $m + n$.\n - line 120: $F^{\\otimes n}$ undefined - I believe the authors mean Kroneker product\n - line 125: \"thatl\"\n - line 231: \"mutual information lower \" - the word \"bound\" is missing\n - line 479: incorrect reference to figure 7, should be figure 8; the contents of figure 7 are never referenced\n - lines 502-503: \"has the correct binomial distribution.\" - I believe it should be bernoulli\n - Eqs (21) and (22): Indicator has $Z_i$ instead of $Z_1$ and $Z_2$\n - Figs 1a & b are difficult to read; please increase the font size of the axis, tick and legend labels\n - I think the left and right panels of Figure 2 could be merged\n - Please add an explicit reference to the proof of Theorem 1 in Appendix C.\n - Eq (28): I believe the expression should be $I[U_2 ; Y_1, Y_2, \\mid U_1]$, unless $U_1$ is independent of $U_2$. Given Eq (17), it makes sense, but the authors should mention this explicitly.\n - Regarding the proof of Theorem 1 in Appendix C: \n   - Please restate the theorem in the appendix.\n   - Why does eq 53 mix the two probability notations?\n   - I believe Eq (54) is an equality rather than an inequality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging feedback, and for suggesting the improvement to our comparison plot.\n> ...  description of the experimental setup ...\n\nWe will describe the experimental setup for Figure 3 here, which we will also include in the camera-ready version of the paper. This also takes into account the reviewer's suggestion for speeding up the implementation of GPRS and PFR. The updated plot is included in the attached PDF (Please refer to Figure 2).\n1. $\\mathtt{PolarSim}$: We use the same setup used in the BSC plots for Figure 2 (i.e. the top plots). We plot the average rate over 200 simulation runs.\n2. **GPRS**: We implement [7, Alg. 3]. The proposal distribution $P$ is chosen to be i.i.d. Bernoulli($1/2$) with $n = 8$. Given the input $X^n = x^n$, the target distribution $Q(y^n)$ is chosen to be $\\prod_{i = 1}^n \\mathsf{BSC}_p(y_i|x_i)$, where $p$ ranges over $(0,1/2)$. The stretch function $\\sigma$ was derived using the definitions provided in [7]: $w_P(h) = F\\left(\\frac{\\log h - n( \\log(1-p) + 1 )}{\\log p - \\log(1 - p)}, n, \\frac{1}{2}\\right)$, $w_Q(h) = F\\left(\\frac{\\log h - n( \\log(1-p) + 1 )}{\\log p -\\log(1 - p)}, n, p\\right)$, and $\\sigma(h) = \\int_0^h \\frac{1}{w_Q(\\eta) - \\eta w_P(\\eta)}d\\eta$ where $F(\\cdot,n,p)$ is the CDF of a $\\text{Binomial}(n,p)$ random variable.\nThe algorithm outputs a positive integer $n$, which is entropy coded using the Zeta distribution in [(151), 7]. The number of bits is divided by $n = 8$ to obtain the rate. For each $p$ on a grid in $(0, \\frac{1}{2})$, we run the simulation $200$ times and plot the average rate obtained against the channel mutual information $1 - H(p)$. We observe that the selection rule used by the algorithm can overlook repetitions --- if the first occurrence of an output sequence in the randomly generated codebook is rejected, all its subsequent occurrences are also rejected. This simplification helps speed up the execution significantly and also reduces the rate as repetitions need not be indexed.\n\n3. **PFR**: We use the algorithm described in  [Sections II-III, 1] with $P_Y$ chosen to be i.i.d. Bernoulli($1/2$) \n    with $n = 8$ and $P_{Y|X}$ chosen to be i.i.d. BSCs with crossover probability $p$. We use the same idea as outlined before in the GPRS implementation to eliminate repetitions from the codebook, speeding up the algorithm and improving the rate. The selected index $n$ is compressed using the Zipf distribution given in [Sec. III, 1]. We simulate the channel $200$ times for uniformly randomly chosen input sequences and plot the average rate obtained.\n\n> ... contents of Appendix A ...\n\nProposed algorithm:\n1. Let $X^n \\sim \\mathcal{N}(0,\\sigma^2)$ be the input at the encoder, and $f^*(\\cdot, R)$ be a rate $R$ trellis coded quantizer that obtains an average distortion value of $D$. We use a $256$-state trellis with each state having exactly two branches leaving it, along with a codebook of size $2^{R+1}$ which is partitioned into 4 subsets, each of size $2^{R-1}$. Each branch of the trellis is then associated with one of the $4$ subsets (See [Figure 3.15, 14] for the mapping used). The Trellis is initialized with randomly generated codewords from a standard normal and trained using the Lloyd-Max algorithm. Please refer to [14] for a detailed description of the Trellis construction and training.\n\n2. Using the common randomness, select a uniformly random rotation matrix $\\Pi$ at both the encoder and decoder.\n\n3. At the encoder, compute the randomly rotated source $\\tilde{X}^n = \\Pi X^n$ and the reconstruction $\\hat{\\tilde{X}}^n = f(\\tilde{X}^n, R)$. Transmit the reconstruction to the decoder by specifying its trellis path.\n4. Compute the scaling factor $a = \\frac{\\sigma^2}{\\sigma^2 - D}$ and the reconstruction $\\tilde{Y}^n = a\\hat{\\tilde{X}}^n$\n5. Finally, compute $Y^n = \\Pi^{-1}\\tilde{Y}^n$ as the output of the scheme.\n\nIn figure 4, we generate $100$ independent realizations of $X^n$ with $n=1000$ and source power $\\sigma^2 = 1$. The scheme outlined above is then used to generate the corresponding $Y^n$ realizations. The quantiles of the sample noise $D = \\|| X^n - Y^n \\||^2$ are plotted against the theoretical quantiles obtained by assuming $p_{Y|X}$ to be AWGN with noise power $\\frac{1}{n}\\sum\\limits_{i=1}^{n}\\|| X_i^n - Y_i^n \\||^2$.\n\nIn Figure 5, we plot the rate of our approximate scheme against the mutual information of the simulated channel. Bootstrapped $95\\%$ile confidence intervals for the mutual information are plotted to account for the error in estimating the noise power.\n> ... analytic form of the mutual information ...\n\n1. $p_{Y|X}$ is $\\mathsf{BSC(p)}$, $p_X$ is $\\text{Unif}(\\{0,1\\})$}: $I(X;Y) = 1 - H(p)$\n2. $p_{Y|X}$ is $\\mathsf{BEC(\\epsilon)}$, $p_X$ is $\\text{Unif}(\\{0,1\\})$}: $I(X;Y) = 1 - \\epsilon$\n3. $p_{Y|X}$ is $\\mathsf{AWGN(\\sigma^2)}$, $p_X$ is $\\text{Unif}(\\{-1,1\\})$}: There is no known closed-form expression for the mutual information in this case. We note that $p_Y(y) = \\frac{1}{2}\\mathcal{N}(y|-1, \\sigma^2) + \\frac{1}{2}\\mathcal{N}(y|1, \\sigma^2)$, $p_{Y|X}(y|x = 1) = \\mathcal{N}(y|1, \\sigma^2)$, and $p_{Y|X}(y|x = -1) = \\mathcal{N}(y|-1, \\sigma^2)$. We can then calculate $h(Y)$ using numerical integration and observe that $h(Y|X) = \\frac{1}{2}h(Y|X=1) + \\frac{1}{2}h(Y|X=-1) = \\frac{\\ln 2}{2} \\left[ 1 + \\ln{ 2\\sigma^2\\pi } \\right]$. From these, we can compute $I(X;Y) = h(Y) - h(Y|X)$.\n\n>...polarization occurs for large $n$, ..\n\nTo clarify, the claim in the paper was that, for a fixed channel, polarization increases with the number of i.i.d. copies, $n$ (Figure 1 of uploaded PDF).\n\nWe did not intend to suggest that polarization occurs as $n$ increases if the channel varies with $n$, say by holding $nI(X;Y)$ fixed. In our experience, noisier channels polarize more slowly. If one increases $n$ and the channel noise simultaneously, it is unclear which of these effects will dominate.\n\nThank you for highlighting various typos and errors. We will correct them in the final draft.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for taking the time to review our paper. Their feedback and suggestions will be valuable in helping us refine our work.

Based on their comments, these emerged as the main areas for improvement for our paper:
* Studying the performance of $\mathtt{PolarSim}$ for small $n$ . 
* Simplifying our description in Section 3. to avoid any potential confusion regarding the directionality of the simulated channel
* Our comparison plot (Figure 3 in the paper)
   * Providing full details of our experiments for greater reproducibility
   * investigating/fixing the convergence issues for GPRS
* Providing full experimental details for the scheme presented in Appendix A

 We have detailed our strategy to tackle these issues in our responses to the individual reviewers. We have also addressed other questions and clarifications that were raised in the reviews.

# Supplementary PDF
We have also included a one-page PDF attachment that contains the following figures
* Figure 1 contains plots of the normalized redundancy $R_n - I(X;Y)$ vs the blocklength $n$ for three different channels.
* Figure 2 contains an updated plot of Figure 3 from the paper, based on the suggestions offered by Reviewer w9ei. 

# References
1. Cheuk Ting Li and Abbas El Gamal, "Strong functional representation lemma and applications to coding theorems", *IEEE Transactions on Information Theory*, 2018.
2. Chris J. Maddison, Daniel Tarlow, and Tom Minka, "$A^*$ sampling,'' *NeurIPS*, 2014.
3. Eirikur Agustsson and Lucas Theis, "Universally quantized neural compression,'' *NeurIPS*, 2020.
4. Gergely Flamich, Stratis Markou, and José Miguel Hernández-Lobato, "Fast relative entropy coding with $A^*$ coding,'' *ICML*, 2022.
5. Lucas Theis and Noureldin Yosri, "Algorithms for the communication of samples,'' *ICML*, 2022.
6. Gergely Flamich, Stratis Markou, and José Miguel Hernández-Lobato, "Faster relative entropy coding with greedy rejection coding.'' *NeurIPS*, 2023.
7. Gergely Flamich, "Greedy Poisson rejection sampling,'' *NeurIPS*, 2024.
8. Buu Phan, Ashish Khisti, and Christos Louizos, "Importance matching lemma for lossy compression with side information,'' *AISTATS*, 2024.
9. Braverman and Garg, "Public vs private coin in bounded-round information'', *ICALP*, 2014
10. Sharang M Sriramu and Aaron B Wagner, "Optimal redundancy in exact channel synthesis", *arXiv
preprint*, 2024.
11. J. T. Rolfe, "Discrete Variational Autoencoders'', *ICLR*,  2017
12. J. Fajtl, V. Argyriou, D. Monekosso and P. Remagnino, "Latent Bernoulli Autoencoder'', *ICML*, 2020.
13. E. Özyilkan, J. Ballé, and E. Erkip, “Learned Wyner–Ziv compressors recover binning”, *ISIT*, 2023.
14. David S Taubman, Michael W Marcellin, "JPEG2000: Image compression fundamentals, standards and practice", *Springer*, 2002.

Meta-review: This paper proposes a practically-implementable scheme for channel simulation, which uses polar codes.

The rating/confidence scores of the reviewers were 8/1, 4/2, 4/4, and 7/4, showing a relatively large split.
I would like to note that such a large split is not uncommon for papers on interdisciplinary topics, like this one.
I have read this paper myself, as well as the reviews and discussion with the authors. Besides the clarity issues and the weakness in the experimental section (they were on a few basic channel models, and no machine-learning related experiments were conducted), as raised by some reviewers, I have a few additional concerns:
- **Polar codes:** The proposed scheme does not use polar codes but just channel polarization, or more precisely, channel polarization in terms of mutual information.
I think that this point is important, because it makes the successive-cancellation (SC) decoding and the rate of polarization unnecessary in this paper, although they are needed to prove the capacity-achieving property (i.e., that the block-error rate can be made arbitrarily small as the codelength tends to infinity) of polar codes. Clarification on this point will avoid possible misunderstanding (e.g., why do not existing non-polarizing channels when $n$ is not large enough cause any problem, why is the stochastic sampling (SoftPolarDec) used instead of SC decoding, etc.) of those who are knowledgeable about polar codes.
- **Experiments:** My understanding of the proposed scheme is: Given a channel, one first performs channel polarization transform recursively to obtain $n$ polarized subchannels. One then evaluates the subchannel parameters $\bar{p}^n$. The rate is then determined *a posteriori* via e.g. arithmetic coding. In Figure 2, however, the parameters to be adjusted are shown in the vertical axes, and the resulting rates are shown in the horizontal axes, which is just the opposite of the common convention of taking the independent variable in the horizontal axis and the dependent variable in the vertical axis. I also guess that the percentiles shown in Figure 2 result from the variable-length nature of arithmetic coding, which is not explained explicitly.

After the discussion among us did not resolve the large split in the scores, but the agreement we have reached is that the significance would outweigh those weaknesses raised by the reviewers. I thus would like to recommend acceptance of this paper, on the premise that the points raised by the reviewers will be properly addressed in the final version.

Minor points:
- Line 21: or (or)
- Line 55: (it) means that
- Line 79: What does "balance" mean?
- Line 85: The notation $p^{\times n}$ using the superscript "$\times n$" is not restricted to the channels, as can be seen on line 93, where it is applied to the input distribution $p_X$.
- Line 89: 1 → $p$
- Line 99: $m+n\mathrm{y}$ → $m+n$
- Line 123: "accordingly" is not clear enough; that(l)
- Line 128: $0$, $1/2$, or $1$ → $0$, $1$, or $\infty$
- Lines 142-147: Under the channel model assumed here, $(X_i,Y_i)$ are not iid, so that, strictly speaking, one cannot apply equation (3) directly here.
- Line 152: It would be better if the authors introduce the symbols $V_i$ and $Δ_i$ to denote a common bit and a difference bit, respectively.
- Line 154: suffices to send (it) $Δ^n$
- Equations (21) and (22): $Z_i$ → $Z_1$ or $Z_2$
- Equation (22): Whether the value of $U_1$ generated according to equation (21) is to be used as $u_1$ appearing in the conditioning part of equation (22) is not clear.
- Line 187: in (in)
- Algorithm 2: $N$ → $n$
- Line 227: $N(0,\sigma^2$ → $N(0,\sigma^2)$
- Line 231: mutual information lower (bound)
- Line 398: a AWGNchannel → an AWGN channel
- Line 400: developed (by) as
- Line 407: $\{1\ldots k\}$ → $\{1,\ldots,k\}$
- Equation (54): Some explanation on how to derive it using equations (48)-(52) would be beneficial, as it may be confused with "mismatched entropy", represented as a sum of the true entropy and the KL divergence.
Decision: Accept (poster)