Channel Simulation: Theory and Applications to Lossy Compression and Differential Privacy

One-shot channel simulation, or channel synthesis, has seen increasing applications in lossy compression, differential privacy and machine learning. In this setting, an encoder observes a source X, and transmits a description to a decoder, so as to allow it to produce an output Y with a desired conditional distribution P_YX. In other words, the encoder and the decoder are simulating the noisy channel P_YX using noiseless communication. This can also be seen as a lossy compression scheme with a stronger guarantee on the joint distribution of X and Y. This monograph gives an overview of the theory and applications of the channel simulation problem. A unifying review of various one-shot and asymptotic channel simulation techniques that have been proposed in different areas are presented, namely dithered quantization, rejection sampling, minimal random coding, likelihood encoder, soft covering, Poisson functional representation, and dyadic decomposition.