Thank you for your encouraging feedback, and for suggesting the improvement to our comparison plot.

... description of the experimental setup ...

We 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).

1. $\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.

2. 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. The 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.

3. PFR: We use the algorithm described in [Sections II-III, 1] with $P_Y$ chosen to be i.i.d. Bernoulli($1/2$) 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.

... contents of Appendix A ...

Proposed algorithm:

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

2. Using the common randomness, select a uniformly random rotation matrix $\Pi$ at both the encoder and decoder.

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

4. Compute the scaling factor $a = \frac{\sigma^2}{\sigma^2 - D}$ and the reconstruction $\tilde{Y}^n = a\hat{\tilde{X}}^n$

5. Finally, compute $Y^n = \Pi^{-1}\tilde{Y}^n$ as the output of the scheme.

In 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$.

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

... analytic form of the mutual information ...

1. $p_{Y|X}$ is $\mathsf{BSC(p)}$, $p_X$ is $\text{Unif}(\{0,1\})$}: $I(X;Y) = 1 - H(p)$
2. $p_{Y|X}$ is $\mathsf{BEC(\epsilon)}$, $p_X$ is $\text{Unif}(\{0,1\})$}: $I(X;Y) = 1 - \epsilon$
3. $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)$.

...polarization occurs for large $n$, ..

To 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).

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

Thank you for highlighting various typos and errors. We will correct them in the final draft.

Thank you for your feedback. We address your comments and questions below:

... This topic has been extensively explored in the information theory literature ...

We 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].

... the problem formulation, proposed solution, and underlying applications do not align with the core focus areas of this conference ...

Again we disagree:

• The problem formulation is drawn directly from the above papers
• The proposed solution is more of interest to the ML community because it proposes a fast, implementable scheme
• The applications mentioned in the second paragraph of the introduction are all drawn from machine learning, with citations to papers in ML venues.

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

The problem formulation is not rigorously provided

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

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

... many of the statements and proofs are incomplete and inaccurate.

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

The proposed approach lacks significant novelty.

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

... restricted to the synthesis of symmetric binary-input channels

The channel must be binary output, not binary input. Otherwise, we agree that this is a limitation of the paper. But, we note that

1. No existing scheme can achieve subexponential complexity for any nontrivial class of channels.
2. 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.
3. For compression applications, binary-output channels are not unreasonable. Indeed, various papers have considered VAE-type architectures with discrete latents, including [11-13].

In 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].

The IID assumption ...

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

Please explain why the paper focuses on polar codes ...

The focus on polar codes is made clear in the introduction of the paper:

"First, they [polar codes] have excellent channel coding performance, both 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."

PolarSim relies on certain unique properties of polar codes; it does not extend to arbitrary linear codes.

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

Also, note that the decoding complexity of polar codes is $n \log n$. It is low, not high.

Common randomness ...

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

Section III ...

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

The simulation of the reverse channel ...

The 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}$.

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

We also thank you for pointing out typos and errors; we will correct them in the final draft.

Thank you for your feedback and comments. We have addressed specific comments and questions below.

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

What is the meaning of the performance?

How to justify "fast'' in the title?

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

We 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$."

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

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.

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?

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

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?

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

Could the authors repeat their contributions in Conclusions so the contributions are clearer?

Thank you for this suggestion. We will take this into consideration when preparing the camera-ready version.

The figures would be easier to read if the colors were included in a legend within the plot.

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

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