Distributed Channel Synthesis

Abstract

Two familiar notions of correlation are rediscovered as the extreme operating points for distributed synthesis of a discrete memoryless channel, in which a stochastic channel output is generated based on a compressed description of the channel input. Wyner's common information is the minimum description rate needed. However, when common randomness independent of the input is available, the necessary description rate reduces to Shannon's mutual information. This work characterizes the optimal trade-off between the amount of common randomness used and the required rate of description. We also include a number of related derivations, including the effect of limited local randomness, rate requirements for secrecy, applications to game theory, and new insights into common information duality. Our proof makes use of a soft covering lemma, known in the literature for its role in quantifying the resolvability of a channel. The direct proof (achievability) constructs a feasible joint distribution over all parts of the system using a soft covering, from which the behavior of the encoder and decoder is inferred, with no explicit reference to joint typicality or binning. Of auxiliary interest, this work also generalizes and strengthens this soft covering tool.

To appear in IEEE Trans. on Information Theory (submitted Aug., 2012, accepted July, 2013), 26 pages, using IEEEtran.cls

References in corpus (8)

• The information-theoretic costs of simulating quantum measurements
• Communication Requirements for Generating Correlated Random Variables
• Achievability proof via output statistics of random binning
• Secrecy Is Cheap if the Adversary Must Reconstruct
• Coordination via a relay
• State Information in Bayesian Games
• A Connection between Good Rate-distortion Codes and Backward DMCs
• On Secure Communication with Constrained Randomization

Cited by in corpus (53)

• Covert Communication over Noisy Channels: A Resolvability Perspective
• The Likelihood Encoder for Lossy Compression
• Exact Random Coding Secrecy Exponents for the Wiretap Channel
• Identifying the Information Gain of a Quantum Measurement
• A Unified Framework for One-shot Achievability via the Poisson Matching Lemma
• Neural Estimation of the Rate-Distortion Function With Applications to Operational Source Coding
• A Stronger Soft-Covering Lemma and Applications
• Strong coordination of signals and actions over noisy channels with two-sided state information
• Efficient Approximate Minimum Entropy Coupling of Multiple Probability Distributions
• Multiple Access Channel Simulation
• Generalized Common Informations: Measuring Commonness by the Conditional Maximal Correlation
• Quantum soft-covering lemma with applications to rate-distortion coding, resolvability and identification via quantum channels
• Strong Coordination over Multi-hop Line Networks
• Non-Asymptotic and Second-Order Achievability Bounds for Coding With Side-Information
• Secret Key Generation with One Communicator and a One-Shot Converse via Hypercontractivity
• One-Shot Mutual Covering Lemma and Marton's Inner Bound with a Common Message
• Channel Simulation: Finite Blocklengths and Broadcast Channels
• Gaussian Approximation of Quantization Error for Estimation from Compressed Data
• Interactive Secure Function Computation
• A unified approach to source and message compression
• The Likelihood Encoder for Source Coding
• Strong Converse and Second-Order Asymptotics of Channel Resolvability
• Achievability proof via output statistics of random binning
• Smoothing of binary codes, uniform distributions, and applications
• Resolvability in Eγ with Applications to Lossy Compression and Wiretap Channels
• Strong Coordination over Noisy Channels
• Key Capacity for Product Sources with Application to Stationary Gaussian Processes
• Coordination Through Shared Randomness
• Strong Coordination over Noisy Channels: Is Separation Sufficient?
• Deep Randomized Distributed Function Computation (DeepRDFC): Neural Distributed Channel Simulation
• Gaussian Secure Source Coding and Wyner's Common Information
• Optimal Communication Rates and Combinatorial Properties for Common Randomness Generation
• On Exact and $\infty$-Rényi Common Informations
• Joint Coordination-Channel Coding for Strong Coordination over Noisy Channels Based on Polar Codes
• Scalable Capacity Bounding Models for Wireless Networks
• Exact Channel Synthesis
• Joint Source-Channel Secrecy Using Hybrid Coding
• Covert Communication Over a Compound Channel
• Extended Gray-Wyner System with Complementary Causal Side Information
• Wyner's Common Information under Rényi Divergence Measures
• Asymptotic Coupling and Its Applications in Information Theory
• On the compression of messages in the multi-party setting
• One-Shot Distributed Source Simulation: As Quantum as it Can Get
• Bounds on Covert Capacity with Sub-Exponential Random Slot Selection
• Distributed Source Simulation With No Communication
• Channel simulation via interactive communications
• One-shot Multiple Access Channel Simulation
• Randomized Distributed Function Computation (RDFC): Ultra-Efficient Semantic Communication Applications to Privacy
• Strong Coordination over a Line Network
• Undetectable Radios: Covert Communication under Spectral Mask Constraints
• Secrecy in Cascade Networks
• Covert Identification over Binary-Input Discrete Memoryless Channels
• A New Wiretap Channel Model and its Strong Secrecy Capacity