We propose using confusion hypergraph (hyperconfusion) as a model of information. In contrast to the conventional approach using random variables, we can now perform conjunction, disjunction and implication of information, forming a Heyting algebra. Confusion hypergraphs have an interpretation similar to propositions in generalized inquisitive logic. Using the connection between Heyting algebra and intuitionistic logic, we can express the requirements of a communication network (e.g., network coding, index coding, Slepian-Wolf coding) as a logical formula, allowing us to use the hypergraph Heyting algebra to directly compute the optimal coding scheme. The optimal communication cost is simply given by the entropy of the hypergraph (within a logarithmic gap). This gives a surprising correspondence between coding settings and logical formulae, similar to the Curry-Howard correspondence between computer programs and proofs.

We introduce the one-cold Poisson channel (OCPC), where the transmitter chooses one of several frequency bands to attenuate at a time. In particular, the perfect OCPC, where the number of bands is unlimited, is an extremely simple continuous-time memoryless channel. It has a capacity 1, zero channel dispersion, and an information spectrum being the degenerate distribution at 1. It is the only known nontrivial (discrete or continuous-time) memoryless channel with a closed-form formula for its optimal non-asymptotic error probability, making it the simplest channel in this sense. A potential application is optical communication with a tunable band rejection filter. Due to its simplicity, we may use it as a basic currency of information that is infinitely divisible, as an alternative to bits which are not infinitely divisible. OCPC with perfect feedback gives a generalization of prefix codes. We also study non-asymptotic coding and channel simulation results for the general OCPC.

We propose a framework for second-order achievability, called type deviation convergence, that is generally applicable to settings in network information theory, and is especially suitable for lossy source coding and channel coding with cost. We give a second-order achievability bound for lossy source coding with side information at the decoder (Wyner-Ziv problem) that improves upon all known bounds (e.g., Watanabe-Kuzuoka-Tan, Yassaee-Aref-Gohari and Li-Anantharam). We also give second-order achievability bounds for lossy compression where side information may be absent (Heegard-Berger problem) and channels with noncausal state information at the encoder and cost constraint (Gelfand-Pinsker problem with cost) that improve upon previous bounds.

The information bottleneck channel (or the oblivious relay channel) concerns a channel coding setting where the decoder does not directly observe the channel output. Rather, the channel output is relayed to the decoder by an oblivious relay (which does not know the codebook) via a rate-limited link. The capacity is known to be given by the information bottleneck. We study finite-blocklength achievability results of the channel, where the relay communicates to the decoder via fixed-length or variable-length codes. These two cases give rise to two different second-order versions of the information bottleneck. Our proofs utilize the nonasymptotic noisy lossy source coding results by Kostina and Verdú, the strong functional representation lemma, and the Poisson matching lemma. Moreover, we also give a novel nonasymptotic variable-length noisy lossy source coding result.

A fine-grained comparison of generative models requires the identification of sample types generated differently by each of the involved models. While quantitative scores have been proposed in the literature to rank different generative models, score-based evaluation and ranking do not reveal the nuanced differences between the generative models in producing different sample types. In this work, we propose solving a differential clustering problem to detect sample types generated differently by two generative models. To solve the differential clustering problem, we develop a spectral method called Fourier-based Identification of Novel Clusters (FINC) to identify modes produced by a generative model with a higher frequency in comparison to a reference distribution. FINC provides a scalable algorithm based on random Fourier features to estimate the eigenspace of kernel covariance matrices of two generative models and utilize the principal eigendirections to detect the sample types present more dominantly in each model. We demonstrate the application of the FINC method to large-scale computer vision datasets and generative modeling frameworks. Our numerical results suggest the scalability of the developed Fourier-based method in highlighting the sample types produced with different frequencies by generative models. The project code is available at https://github.com/buyeah1109/FINC

The availability of multiple training algorithms and architectures for generative models requires a selection mechanism to form a single model over a group of well-trained generation models. The selection task is commonly addressed by identifying the model that maximizes an evaluation score based on the diversity and quality of the generated data. However, such a best-model identification approach overlooks the possibility that a mixture of available models can outperform each individual model. In this work, we numerically show that a mixture of generative models on benchmark image datasets can indeed achieve a better evaluation score (based on FID and KID scores), compared to the individual models. This observation motivates the development of efficient algorithms for selecting the optimal mixture of the models. To address this, we formulate a quadratic optimization problem to find an optimal mixture model achieving the maximum of kernel-based evaluation scores including kernel inception distance (KID) and Rényi kernel entropy (RKE). To identify the optimal mixture of the models using the fewest possible sample queries, we view the selection task as a multi-armed bandit (MAB) problem and propose the *Mixture Upper Confidence Bound (Mixture-UCB)* algorithm that provably converges to the optimal mixture of the involved models. More broadly, the proposed Mixture-UCB can be extended to optimize every convex quadratic function of the mixture weights in a general MAB setting. We prove a regret bound for the Mixture-UCB algorithm and perform several numerical experiments to show the success of Mixture-UCB in finding the optimal mixture of text and image generative models. The project code is available in the [Mixture-UCB Github repository](https://github.com/Rezaei-Parham/Mixture-UCB).

We study a quantity called discrete layered entropy, which approximates the Shannon entropy within a logarithmic gap. Compared to the Shannon entropy, the discrete layered entropy is piecewise linear, approximates the expected length of the optimal one-to-one non-prefix-free encoding, and satisfies an elegant conditioning property. These properties make it useful for approximating the Shannon entropy in linear programming and maximum entropy problems, studying the optimal length of conditional encoding, and bounding the entropy of monotonic mixture distributions. In particular, it can give a bound for the strong functional representation lemma that improves upon the best known bound (as long as the mutual information is at least 2). A full version of this paper is accessible at [1].

The information bottleneck channel (or the oblivious relay channel) concerns a channel coding setting where the decoder does not directly observe the channel output. Rather, the channel output is relayed to the decoder by an oblivious relay (which does not know the codebook) via a rate-limited link. The capacity is known to be given by the information bottleneck. We study finite-blocklength achievability results of the channel, where the relay communicates to the decoder via fixed-length or variable-length codes. These two cases give rise to two different second-order versions of the information bottleneck. Our proofs utilize the nonasymptotic noisy lossy source coding results by Kostina and Verdú, the strong functional representation lemma, and the Poisson matching lemma. Moreover, we also give a novel nonasymptotic variable-length noisy lossy source coding result. A full version of this paper is accessible at [1].

Information diagrams and the I-measure are useful mnemonics where random variables are treated as sets, and entropy and mutual information are treated as a signed measure. Although the I-measure has been successful in machine proofs of entropy inequalities, the theoretical underpinning of the “random variables as sets” analogy has been unclear until the recent works on mappings from random variables to sets by Ellerman (recovering order-2 Tsallis entropy over general probability space), and Down and Mediano (recovering Shannon entropy over discrete probability space). We generalize these constructions by designing a mapping which recovers the Shannon entropy (and the information density) over general probability space. Moreover, it has an intuitive interpretation based on the arrival time in a Poisson process, allowing us to understand the union, intersection and difference between (sets corresponding to) random variables and events. Cross entropy, KL divergence, and conditional entropy given an event, can be obtained as set intersections. We propose a generalization of the information diagram that also includes events, and demonstrate its usage by a diagrammatic proof of Fano’s inequality.

We construct a randomized vector quantizer which has a smaller maximum error compared to all known lattice quantizers with the same entropy for dimensions 5, 6, ..., 48, and also has a smaller mean squared error compared to known lattice quantizers with the same entropy for dimensions 35, ..., 47, in the high resolution limit. Moreover, our randomized quantizer has a desirable property that the quantization error is always uniform over the ball and independent of the input. Our construction is based on applying rejection sampling on universal quantization, which allows us to shape the error distribution to be any continuous distribution, not only uniform distributions over basic cells of a lattice as in conventional dithered quantization. We also characterize the high SNR limit of one-shot channel simulation for any additive noise channel under a mild assumption (e.g., the AWGN channel), up to an additive constant of 1.45 bits.

We present a unified one-shot coding framework designed for the communication and compression of messages among multiple nodes across a general acyclic noisy network. Our setting can be seen as a one-shot version of the acyclic discrete memoryless network studied by Lee and Chung, and noisy network coding studied by Lim, Kim, El Gamal and Chung. We design a proof technique, called the exponential process refinement lemma, that is rooted in the Poisson matching lemma by Li and Anantharam, and can significantly simplify the analyses of one-shot coding over multi-hop networks. Our one-shot coding theorem not only recovers a wide range of existing asymptotic results, but also yields novel one-shot achievability results in different multi-hop network information theory problems, such as compress-and-forward and partial-decode-and-forward bounds for a one-shot (primitive) relay channel, and a bound for one-shot cascade multiterminal source coding. In a broader context, our framework provides a unified one-shot bound applicable to any combination of source coding, channel coding and coding for computing problems.

Compression schemes have been extensively used in Federated Learning (FL) to reduce the communication cost of distributed learning. While most approaches rely on a bounded variance assumption of the noise produced by the compressor, this paper investigates the use of compression and aggregation schemes that produce a specific error distribution, e.g., Gaussian or Laplace, on the aggregated data. We present and analyze different aggregation schemes based on layered quantizers achieving exact error distribution. We provide different methods to leverage the proposed compression schemes to obtain compression-for-free in differential privacy applications. Our general compression methods can recover and improve standard FL schemes with Gaussian perturbations such as Langevin dynamics and randomized smoothing.

The zero-sum game in generative adversarial networks (GANs) for learning the distribution of observed data is known to reduce to the minimization of a divergence measure between the underlying and generative models. However, the current theoretical understanding of the role of the target divergence in the characteristics of GANs’ generated samples remains largely inadequate. In this work, we aim to analyze the influence of the divergence measure on the local optima and convergence properties of divergence minimization problems in learning a multi-modal data distribution. We show a mode-seeking f-divergence, e.g. the Jensen-Shannon (JS) divergence in the vanilla GAN, could lead to poor locally optimal solutions missing some underlying modes. On the other hand, we demonstrate that the optimization landscape of 1-Wasserstein distance in Wasserstein GANs does not suffer from such suboptimal local minima. Furthermore, we prove that a randomly-initialized gradient-based optimization of the Wasserstein distance will, with high probability, capture all the existing modes. We present numerical results on standard image datasets, revealing the success of Wasserstein GANs compared to JS-GANs in avoiding suboptimal local optima under a mixture model.

We propose the first method that realizes the Laplace mechanism exactly (i.e., a Laplace noise is added to the data) that requires only a finite amount of communication (whereas the original Laplace mechanism requires the transmission of a real number) while guaranteeing privacy against the server and database. Our mechanism can serve as a drop-in replacement for local or centralized differential privacy applications where the Laplace mechanism is used. Our mechanism is constructed using a random quantization technique. Unlike the simple and prevalent Laplace-mechanism-then-quantize approach, the quantization in our mechanism does not result in any distortion or degradation of utility. Unlike existing dithered quantization and channel simulation schemes for simulating additive Laplacian noise, our mechanism guarantees privacy not only against the database and downstream, but also against the honest but curious server which attempts to decode the data using the dither signals.

The massive developments of generative model frameworks require principled methods for the evaluation of a model's novelty compared to a reference dataset. While the literature has extensively studied the evaluation of the quality, diversity, and generalizability of generative models, the assessment of a model's novelty compared to a reference model has not been adequately explored in the machine learning community. In this work, we focus on the novelty assessment for multi-modal distributions and attempt to address the following differential clustering task: Given samples of a generative model $P_\mathcal{G}$ and a reference model $P_\mathrm{ref}$, how can we discover the sample types expressed by $P_\mathcal{G}$ more frequently than in $P_\mathrm{ref}$? We introduce a spectral approach to the differential clustering task and propose the Kernel-based Entropic Novelty (KEN) score to quantify the mode-based novelty of $P_\mathcal{G}$ with respect to $P_\mathrm{ref}$. We analyze the KEN score for mixture distributions with well-separable components and develop a kernel-based method to compute the KEN score from empirical data. We support the KEN framework by presenting numerical results on synthetic and real image datasets, indicating the framework's effectiveness in detecting novel modes and comparing generative models. The paper's code is available at: github.com/buyeah1109/KEN.

We present a unified one-shot coding framework designed for communication and compression of messages among multiple nodes across a general acyclic noisy network. Our setting can be seen as a one-shot version of the acyclic discrete memoryless network studied by Lee and Chung, and noisy network coding studied by Lim, Kim, El Gamal and Chung. We design a proof technique, called the exponential process refinement lemma, that is rooted in the Poisson matching lemma by Li and Anantharam, and can significantly simplify the analyses of one-shot coding over multi-hop networks. Our one-shot coding theorem not only recovers a wide range of existing asymptotic results, but also yields novel one-shot achievability results in different multi-hop network information theory problems. In a broader context, our framework provides a unified one-shot bound applicable to any combination of source coding, channel coding and coding for computing problems.

Information diagram and the I-measure are useful mnemonics where random variables are treated as sets, and entropy and mutual information are treated as a signed measure. The theoretical underpinning of the “random variables as sets” analogy has been unclear until the recent works on mappings from random variables to sets by Ellerman (recovering order-2 Tsallis entropy over general probability space), and Down and Mediano (recovering Shannon entropy over discrete probability space). We generalize these constructions by designing a mapping which recovers the Shannon entropy (and the information density) over general probability space. Moreover, it has an intuitive interpretation based on the arrival time in a Poisson process, allowing us to understand the union, intersection and difference between (sets corresponding to) random variables and events. Cross entropy, KL divergence, and conditional entropy given an event, can be obtained as set intersections. We propose a generalization of the information diagram that also includes events, and demonstrate its usage by a diagrammatic proof of Fano's inequality.

We construct a randomized vector quantizer which has a smaller maximum error compared to all known lattice quantizers with the same entropy for dimensions 5, 6,…, 48, and also has a smaller mean squared error compared to known lattice quantizers with the same entropy for dimensions 35,…, 48, in the high resolution limit. Moreover, our randomized quantizer has a desirable property that the quantization error is always uniform over the ball and independent of the input. Our construction is based on applying rejection sampling on universal quantization, which allows us to shape the error distribution to be any continuous distribution, not only uniform distributions over basic cells of a lattice as in conventional dithered quantization. We also characterize the high SNR limit of one-shot channel simulation for any additive noise channel under a mild assumption (e.g., the AWGN channel), up to an additive constant of 1.45 bits.

We consider a key agreement setting where two parties observe correlated random sources, and want to agree on a secret key via public discussions. In order to allow the key length to adapt to the realizations of the random sources, we allow the key to be of variable length, subject to a novel variable-length version of the uniformity constraint based on random stopping time. We propose simple, computationally efficient key agreement schemes under the new constraint. The proposed scheme can be considered as the key agreement analogue of variable-length source coding via Huffman coding, and the Knuth-Yao random number generator.

We present a one-shot information-theoretic analysis of the information hiding problem, which has a wide range of applications including watermarking, fingerprinting, steganogra-phy and copyright protection. The problem can be viewed as a game: one party includes an information hider and a decoder, where the former embeds a message into a host data source and introduces some tolerable distortion, and the latter wishes to reconstruct the message; another party is an attacker that is modeled as a noisy channel which aims at removing the hidden information. We derive a one-shot achievability result using the Poisson matching lemma. Unlike previous asymptotic results, our result applies to any distribution of the host data, and any class of attack channels (not necessarily memoryless or ergodic).

To reduce the communication cost of differential privacy mechanisms, we introduce a novel construction, called Poisson private representation (PPR), designed to compress and simulate any local randomizer while ensuring local differential privacy. Unlike previous simulation-based local differential privacy mechanisms, PPR exactly preserves the joint distribution of the data and the output of the original local randomizer. Hence, the PPR-compressed privacy mechanism retains all desirable statistical properties of the original privacy mechanism such as unbiasedness and Gaussianity. Moreover, PPR achieves a compression size within a logarithmic gap from the theoretical lower bound. Using the PPR, we give a new order-wise trade-off between communication, accuracy, central and local differential privacy for distributed mean estimation. Experiment results on distributed mean estimation show that PPR consistently gives a better trade-off between communication, accuracy and central differential privacy compared to the coordinate subsampled Gaussian mechanism, while also providing local differential privacy.

For uniform scalar quantization, the error distribution is approximately a uniform distribution over an interval (which is also a 1-dimensional ball). Nevertheless, for lattice vector quantization, the error distribution is uniform not over a ball, but over the basic cell of the quantization lattice. In this paper, we construct vector quantizers with periodic properties, where the error is uniformly distributed over the n-ball, or any other prescribed set. We then prove upper and lower bounds on the entropy of the quantized signals. We also discuss how our construction can be applied to give a randomized quantization scheme with a nonuniform error distribution.

In this paper, we introduce a new class of codes, called weighted parity-check codes, where each parity-check bit has a weight that indicates its likelihood to be one (instead of fixing each parity-check bit to be zero). It is applicable to a wide range of settings, e.g. asymmetric channels, channels with state and/or cost constraints, and the Wyner-Ziv problem, and can provably achieve the capacity. For the channel with state (Gelfand-Pinsker) setting, the proposed coding scheme has two advantages. First, it achieves the capacity of any channel with state (e.g. asymmetric channels). Second, simulation results show that the proposed code achieves a smaller error rate compared to the nested linear codes. We also discuss a sparse construction where the belief propagation algorithm can be applied to improve the coding efficiency.

Generative adversarial networks (GANs) represent a game between two neural network machines designed to learn the distribution of data. It is commonly observed that different GAN formulations and divergence/distance measures used could lead to considerably different performance results, especially when the data distribution is multi-modal. In this work, we give a theoretical characterization of the mode-seeking behavior of general f-divergences and Wasserstein distances, and prove a performance guarantee for the setting where the underlying model is a mixture of multiple symmetric quasiconcave distributions. This can help us understand the trade-off between the quality and diversity of the trained GANs’ output samples. Our theoretical results show the mode-seeking nature of the Jensen-Shannon (JS) divergence over standard KL-divergence and Wasserstein distance measures. We subsequently demonstrate that a hybrid of JS-divergence and Wasserstein distance measures minimized by Lipschitz GANs mimics the mode-seeking behavior of the JS-divergence. We present numerical results showing the mode-seeking nature of the JS-divergence and its hybrid with the Wasserstein distance while highlighting the mode-covering properties of KL-divergence and Wasserstein distance measures. Our numerical experiments indicate the different behavior of several standard GAN formulations in application to benchmark Gaussian mixture and image datasets.

Access control encryption (ACE) enforces, through a sanitizer as the mediator, that only legitimate sender-receiver pairs can communicate, without the sanitizer knowing the communication metadata, including its sender and recipient identity, the policy over them, and the underlying plaintext. Any illegitimate transmission is indistinguishable from pure noise. Existing works focused on computational security and require trapdoor functions and possibly other heavyweight primitives. We present the first ACE scheme with information-theoretic security (unconditionally against unbounded adversaries). Our novel randomization techniques over matrices realize sanitization (traditionally via homomorphism over a fixed randomness space) such that the secret message in the hidden message subspace remains intact if and only if there is no illegitimate transmission.

For uniform scalar quantization, the error distribution is approximately a uniform distribution over an interval (which is also a 1-dimensional ball). Nevertheless, for lattice vector quantization, the error distribution is uniform not over a ball, but over the basic cell of the quantization lattice. In this paper, we construct vector quantizers where the error is uniform over the n-ball, or any other prescribed set. We then prove bounds on the entropy of the quantized signals.

The evaluation of generative models has received significant attention in the machine learning community. When applied to a multi-modal distribution which is common among image datasets, an intuitive evaluation criterion is the number of modes captured by the generative model. While several scores have been proposed to evaluate the quality and diversity of a model's generated data, the correspondence between existing scores and the number of modes in the distribution is unclear. In this work, we propose an information-theoretic diversity evaluation method for multi-modal underlying distributions. We utilize the R\'enyi Kernel Entropy (RKE) as an evaluation score based on quantum information theory to measure the number of modes in generated samples. To interpret the proposed evaluation method, we show that the RKE score can output the number of modes of a mixture of sub-Gaussian components. We also prove estimation error bounds for estimating the RKE score from limited data, suggesting a fast convergence of the empirical RKE score to the score for the underlying data distribution. Utilizing the RKE score, we conduct an extensive evaluation of state-of-the-art generative models over standard image datasets. The numerical results indicate that while the recent algorithms for training generative models manage to improve the mode-based diversity over the earlier architectures, they remain incapable of capturing the full diversity of real data. Our empirical results provide a ranking of widely-used generative models based on the RKE score of their generated samples.

We resolve three long-standing open problems, namely the (algorithmic) decidability of network coding, the decidability of conditional information inequalities, and the decidability of conditional independence implication among random variables, by showing that these problems are undecidable. The proof utilizes a construction inspired by Herrmann’s arguments on embedded multivalued database dependencies, a network studied by Dougherty, Freiling and Zeger, together with a novel construction to represent group automorphisms on top of the network.

We present a versatile automated theorem proving framework capable of automated discovery, simplification and proofs of inner and outer bounds in network information theory, deduction of properties of information-theoretic quantities (e.g. Wyner and Gács-Körner common information), and discovery of non-Shannon-type inequalities, under a unified framework. Our implementation successfully generated proofs for 32 out of 56 theorems in Chapters 1–14 of the book Network Information Theory by El Gamal and Kim. Our framework is based on the concept of existential information inequalities, which provides an axiomatic framework for a wide range of problems in information theory.

This paper shows that many notions in information theory (e.g. entropy, capacity regions) can be defined using probabilistic independence alone. We consider the first-order theory of random variables with the probabilistic independence relation, which concerns statements consisting only of random variables, the probabilistic independence symbol, logical operators, and existential and universal quantifiers. Although probabilistic independence is the only non-logical relation included, this theory is surprisingly expressive, and is able to express notions such as entropy and cardinality, and interpret the true first-order arithmetic over natural numbers (and hence is undecidable). We also characterize the capacity region for a general class of multiuser coding settings (including broadcast channel, interference channel and relay channel) using a first-order formula, which can be regarded as a “single-letter characterization” of the capacity region of the aforementioned settings (conventional single-letter characterizations are existential formulae, whereas our formula contains both existential and universal quantifiers). We then introduce the linear entropy hierarchy to classify single-letter characterizations according to their complexity.

We consider a network coding setting where some of the messages and edges have fixed alphabet sizes, that do not change when we increase the common alphabet size of the rest of the messages and edges. We prove that the problem of deciding whether such network admits a coding scheme is undecidable. This can be considered as a partial solution to the conjecture that network coding (without fixed-size messages/edges) is undecidable. The proof, which makes heavy use of analogies with digital circuits, is essentially constructing a digital circuit of logic gates and flip-flops within a network coding model that is capable of simulating an arbitrary Turing machine.

This paper shows that many notions in information theory (e.g. entropy, capacity regions) can be defined using probabilistic independence alone. We consider the first-order theory of random variables with the probabilistic independence relation, which concerns statements consisting only of random variables, the probabilistic independence symbol, logical operators, and existential and universal quantifiers. Although probabilistic independence is the only non-logical relation included, this theory is surprisingly expressive, and is able to express notions such as entropy and cardinality, and interpret the true first-order arithmetic over natural numbers (and hence is undecidable). We also characterize the capacity region for a general class of multiuser coding settings (including broadcast channel, interference channel and relay channel) using a first-order formula, which can be regarded as a "single-letter characterization" of the capacity region of the aforementioned settings (conventional single-letter characterizations are existential formulae, whereas our formula contains both existential and universal quantifiers).

We consider a network coding problem where the destination wants to recover the sum of the signals (Gaussian random variables or random finite field elements) at all the source nodes, but the sum must be kept secret from an eavesdropper that can wiretap on a subset of edges. This setting arises naturally in sensor networks, where the secrecy of the sum of the signals (e.g. weights, gradients) may be desired. While the case for finite field can be solved, the case for Gaussian random variables is surprisingly difficult. We give a simple conjecture on the necessary and sufficient condition under which such secret computation is possible for the Gaussian case, and prove the conjecture when the number of wiretapped edges is at most 2.

In this paper, we introduce a new class of codes, called weighted parity-check codes, where each parity-check bit has a weight that indicates its likelihood to be one (instead of fixing each parity-check bit to be zero). It is applicable to a wide range of settings, e.g. asymmetric channels, channels with state and/or cost constraints, and can provably achieve the capacity. For the channel with state (Gelfand-Pinsker) setting, the proposed coding scheme has two advantages compared to the nested linear code. First, it achieves the capacity of any channel with state (e.g. asymmetric channels). Second, simulation results show that the proposed code achieves a smaller error rate compared to the nested linear code.

We design a randomized scalar quantization scheme, where the quantization error is independent of the source and follows any given unimodal distribution (e.g. Gaussian distribution) exactly. We characterize the optimal encoding length of the quantization, and show that our scheme is optimal. This can also be regarded as a one-shot channel simulation setting, where the channel to be simulated is an additive noise channel. Potential applications include neural compression and coupling from the past.

We establish the undecidability of conditional affine information inequalities, the undecidability of the conditional independence implication problem with a constraint that one random variable is binary, and the undecidability of the problem of deciding whether the intersection of the entropic region and a given affine subspace is empty. This is a step towards the conjecture on the undecidability of conditional independence implication. The undecidability is proved via a reduction from the periodic tiling problem (a variant of the domino problem). Hence, one can construct examples of the aforementioned problems that are independent of ZFC (assuming ZFC is consistent).

We study an information analogue of infinitely divisible probability distributions, where the i.i.d. sum is replaced by the joint distribution of an i.i.d. sequence. A random variable$X$is called informationally infinitely divisible if, for any$n\ge 1$, there exists an i.i.d. sequence of random variables$Z_{1},\ldots,Z_{n}$that contains the same information as$X$, i.e., there exists an injective function$f$such that$X=f(Z_{1},\ldots,Z_{n})$. While there does not exist such informationally infinitely divisible discrete random variable, we show that any discrete random variable$X$can be divided into arbitrarily many identical pieces with a multiplicative penalty to the entropy, that is, if we remove the injectivity requirement on$f$, then there exists i.i.d.$Z_{1},\ldots,Z_{n}$and$f$satisfying$X=f(Z_{1},\ldots,Z_{n})$, and the entropy satisfies$H(X)/n\le H(Z_{1})\le 1.59H(X)/n+2.43$bits. Furthermore, we study the case where$X=(Y_{1},\ldots,Y_{m})$is itself an i.i.d. sequence,$m\ge 2$, for which the multiplicative gap 1.59 can be replaced by$1+5\sqrt {(\log m)/m}$. This means that as$m$increases,$(Y_{1},\ldots,Y_{m})$becomes closer to being spectral infinitely divisible in a uniform manner. This can be regarded as an information analogue of Kolmogorov’s uniform theorem. Applications of our result include independent component analysis and distributed storage with a secrecy constraint.

We present a versatile automated theorem proving framework capable of automated proofs of outer bounds in network information theory, automated discovery of inner bounds in network information theory (in conjunction with the method by Lee and Chung), simplification of capacity regions involving auxiliary random variables, automated deduction of properties of information-theoretic quantities (e.g. Wyner and Gács-Körner common information), and automated discovery of non-Shannon-type inequalities, under a unified framework. Our method is based on the linear programming approach for proving Shannon-type information inequalities by Yeung and Zhang, together with a novel pruning method for searching auxiliary random variables. We introduce the concept of existential information inequalities, which provides an axiomatic framework for a wide range of problems in information theory. A full version of this paper is accessible at: https://arxiv.org/pdf/2101.12370.pdf

We consider a variant of the channel simulation problem with a single input and multiple outputs, where Alice observes a probability distribution P from a set of prescribed probability distributions $\mathcal{P}$, and sends a prefix-free codeword W to Bob to allow him to generate n i.i.d. random variables $X_{1}, X_{2}, \ldots, X_{n}$ which follow the distribution P. This can also be regarded as a lossy compression setting for probability distributions. This paper describes encoding schemes for three cases of $P: P$ is a distribution over positive integers, P is a continuous distribution over $[0,1]$ with a non-increasing pdf, and P is a continuous distribution over $[0, \infty)$ with a nonincreasing pdf. We show that the growth rate of the expected codeword length is sub-linear in n when a power law bound is satisfied. An application of multiple-outputs channel simulation is the compression of probability distributions. A full version of this paper is accessible at: https://arxiv.org/pdf/2105.01045.pdf

We establish the undecidability of conditional affine information inequalities, the undecidability of the conditional independence implication problem with a constraint that one random variable is binary, and the undecidability of the problem of deciding whether the intersection of the entropic region and a given affine subspace is empty. This is a step towards the conjecture on the undecidability of conditional independence implication. The undecidability is proved via a reduction from the periodic tiling problem (a variant of the domino problem).A full version of this paper is accessible at: https://arxiv.org/pdf/2104.05634.pdf

Given a collection of probability distributions p1,⋯,pm, the minimum entropy coupling is the coupling X1,⋯,Xm( Xi~ pi) with the smallest entropy H(X1,⋯,Xm). While this problem is known to be NP-hard, we present an efficient algorithm for computing a coupling with entropy within 2 bits from the optimal value. More precisely, we construct a coupling with entropy within 2 bits from the entropy of the greatest lower bound of p1,⋯,pmwith respect to majorization. This construction is also valid when the collection of distributions is infinite, and when the supports of the distributions are infinite. Potential applications of our results include random number generation, entropic causal inference, and functional representation of random variables.

We introduce a fundamental lemma called the Poisson matching lemma, and apply it to prove one-shot achievability results for various settings, namely channels with state information at the encoder, lossy source coding with side information at the decoder, joint source-channel coding, broadcast channels, distributed lossy source coding, multiple access channels and channel resolvability. Our one-shot bounds improve upon the best known one-shot bounds in most of the aforementioned settings (except multiple access channels and channel resolvability, where we recover bounds comparable to the best known bounds), with shorter proofs in some settings even when compared to the conventional asymptotic approach using typicality. The Poisson matching lemma replaces both the packing and covering lemmas, greatly simplifying the error analysis. This paper extends the work of Li and El Gamal on Poisson functional representation, which mainly considered variable-length source coding settings, whereas this paper studies fixed-length settings, and is not limited to source coding, showing that the Poisson functional representation is a viable alternative to typicality for most problems in network information theory.

This paper studies an information-theoretic one-shot variable-length secret key agreement problem with public discussion. Let X and Y be jointly distributed random variables, each taking values in some measurable space. Alice and Bob observe X and Y respectively, can communicate interactively through a public noiseless channel, and want to agree on a key length and a key that is approximately uniformly distributed over all bit sequences with the agreed key length. The public discussion is observed by an eavesdropper, Eve. The key should be approximately independent of the public discussion, conditional on the key length. We show that the optimal expected key length is close to the mutual information I(X;Y) within a logarithmic gap. Moreover, an upper bound and a lower bound on the optimal expected key length can be written down in terms of I(X;Y) only. This means that the optimal one-shot performance is always within a small gap of the optimal asymptotic performance regardless of the distribution of the pair (X,Y). This one-shot result may find applications in situations where the components of an i.i.d. pair source (Xn,Yn) are observed sequentially and the key is output bit by bit, or in situations where the random source is not an i.i.d. or ergodic process.

A multi-resolution quantizer is a sequence of quantizers where the output of a coarser quantizer can be deduced from the output of a finer quantizer. In this paper, we propose an asymptotically scale-invariant multi-resolution quantizer, which performs uniformly across any choice of average quantization step, when the length of the range of input numbers is large. Scale invariance is especially useful in worst case or adversarial settings, ensuring that the performance of the quantizer would not be affected greatly by small changes of storage or error requirements. We also show that the proposed quantizer achieves a tradeoff between rate and error that is arbitrarily close to the optimum.

The classical problem of supervised learning is to infer an accurate estimate of a target variable Y from a measured variable X using a set of labeled training samples. Motivated by the increasingly distributed nature of data and decision making, this paper considers a variation of this classical problem in which the inference is distributed between two nodes, e.g., a mobile device and a cloud, with a rate constraint on the communication between them. The mobile device observes X and sends a description M of X to the cloud, which computes an estimate Y̑ of Y. We follow the recent minimax learning approach to study this inference problem and show that it corresponds to a one-shot minimax noisy lossy source coding problem. We then establish information theoretic bounds on the risk-rate Lagrangian cost, leading to a general method for designing a near-optimal descriptor-estimator pair. A key ingredient in the proof of our result is a refined version of the strong functional representation lemma previously used to establish several one-shot source coding theorems. Our results show that a naive estimate-compress scheme for rate-constrained inference is not optimal in general. When the distribution of (X, Y) is known and the error is measured by the logarithmic loss, our bounds on the risk-rate Lagrangian cost provide a new one-shot operational interpretation of the information bottleneck. We also demonstrate a way to bound the excess risk of the descriptor-estimator pair obtained by our method.

We introduce the Poisson matching lemma and apply it to prove one-shot achievability results for channels with state information at the encoder, lossy source coding with side information at the decoder, joint source-channel coding, broadcast channels, and distributed lossy source coding. Our one-shot bounds improve upon the best known bounds in the aforementioned settings, with shorter proofs in some settings even when compared to the conventional asymptotic typicality approach. The Poisson matching lemma replaces both the packing and covering lemmas. This paper extends the work of Li and El Gamal on Poisson functional representation for variable-length source coding settings, showing that the Poisson functional representation is a viable alternative to typicality for most problems in network information theory.

The classical problem of supervised learning is to infer an accurate predictor of a target variable Y from a measured variable X by using a finite number of labeled training samples. Motivated by the increasingly distributed nature of data and decision making, in this paper we consider a variation of this classical problem in which the prediction is performed remotely based on a rate-constrained description M of X. Upon receiving M, the remote node computes an estimate Y of Y. We follow the recent minimax approach to study this learning problem and show that it corresponds to a one-shot minimax noisy source coding problem. We then establish information theoretic bounds on the risk-rate Lagrangian cost and a general method to design a near-optimal descriptor-estimator pair, which can be viewed as a rate-constrained analog to the maximum conditional entropy principle used in the classical minimax learning problem. Our results show that a naive estimate-compress scheme for rate-constrained prediction is not in general optimal.

We establish the rate region of an extended Gray-Wyner system (EGW) for 2-DMS (X, Y) with two additional decoders having complementary causal side information. We show that the 5-D rate region of the EGW system is equivalent to the 3-D mutual information region consisting of the set of all triples of the form (I(X; U), I(Y; U), I(X, Y; U)) for some pU|X,Y. This correspondence greatly simplifies the exploration of the the extreme points of the rate region. In addition to the operationally significant extreme points of the original Gray-Wyner rate region, which include Wyner's common information, Gács-Körner common information, and the information bottleneck, the extreme points of the rate region for the EGW system also include the Körner graph entropy, the privacy funnel and excess functional information, as well as three new quantities of potential interest. We further show that projections of the mutual information region yield the rate regions for many settings involving a two discrete memoryless source (2-DMS), including lossless source coding with causal side information, distributed channel synthesis, and lossless source coding with a helper. To further motivate the mutual information region itself, we draw analogies between set operations and its extreme points. This allows us to find random variables that can be considered as intersection, difference, and symmetric difference of two random variables. Finally, we establish the rate regions for two related setups to the EGW system, namely, the noncausal EGW system and the lossy EGW system.

This paper shows that for any random variables X and Y, it is possible to represent Y as a function of (X, Z) such that Z is independent of X and I(X; Z| Y) ≤ log(I(X; Y)+1)+4. We use this strong functional representation lemma (SFRL) to establish a tighter bound on the rate needed for one-shot exact channel simulation than was previously established by Harsha et. al., and to establish achievability results for one-shot variable-length lossy source coding and multiple description coding. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand-Pinsker theorem. Finally we present an example in which the SFRL inequality is tight to within 5 bits.

We establish the rate region of an extended Gray-Wyner system for 2-DMS (X, Y) with two additional decoders having complementary causal side information. This extension is interesting because in addition to the operationally significant extreme points of the Gray-Wyner rate region, which include Wyner's common information, Gåcs-Körner common information and information bottleneck, the rate region for the extended system also includes the Körner graph entropy, the privacy funnel and excess functional information, as well as three new quantities of potential interest, as extreme points. To simplify the investigation of the 5-dimensional rate region of the extended Gray-Wyner system, we establish an equivalence of this region to a 3-dimensional mutual information region that consists of the set of all triples of the form (I (X; U), I (Y; U), I (X, Y; U)) for some pu\x, y. We further show that projections of this mutual information region yield the rate regions for many settings involving a 2-DMS, including lossless source coding with causal side information, distributed channel synthesis, and lossless source coding with a helper.

We establish the first known upper bound on the exact and Wyner's common information of n continuous random variables in terms of the dual total correlation between them (which is a generalization of mutual information). In particular, we show that when the pdf of the random variables is log-concave, there is a constant gap of n2 loge + 9n log n between this upper bound and the dual total correlation lower bound that does not depend on the distribution. The upper bound is obtained using a computationally efficient dyadic decomposition scheme for constructing a discrete common randomness variable W from which the n random variables can be simulated in a distributed manner. We then bound the entropy of W using a new measure, which we refer to as the erosion entropy.

Alice selects an arbitrary pdf f and uses a stochastic encoder to generate a prefix-free codeword M, which is sent to Bob so that he can generate a single instance of the random variable X ~ f. We describe a universal coding scheme for this setup which works for any f , and establish an upper bound on its expected codeword length when the pdf f is bounded, orthogonally concave (which includes quasiconcave pdf), and has a finite first absolute moment. A dyadic decomposition scheme is used to express the pdf as a mixture of uniform pdfs over hypercubes. Alice randomly selects a hypercube according to its weight, encodes its position and size into M, and sends it to Bob who generates X uniformly over the hypercube. Compared to previous results on channel simulation, our coding scheme applies to any continuous distribution and does not require two-way communication or shared randomness. Applying our coding scheme to classical simulation of quantum entanglement, we obtain a tighter bound on the average codeword length than previously known.

We consider vector space interference alignment strategies over the$K$-user interference channel and derive an upper bound on the achievable degrees of freedom as a function of the channel diversity$L$, where the channel diversity is modeled by$L$real-valued parallel channels with coefficients drawn from a nondegenerate joint distribution. The seminal work of Cadambe and Jafar shows that when$L$is unbounded, vector space interference alignment can achieve 1/2 degrees of freedom per user independent of the number of users$K$. However, wireless channels have limited diversity, in practice, dictated by their coherence time and bandwidth, and an important question is the number of degrees of freedom achievable at finite$L$. When$K=3$and if$L$is finite, Bresleret al.show that the number of degrees of freedom achievable with vector space interference alignment is bounded away from 1/2, and the gap decreases inversely proportional to$L$. In this paper, we show that when$K\geq 4$, the gap is significantly larger. In particular, the gap to the optimal 1/2 degrees of freedom per user can decrease at most like$1/\sqrt {L}$, and when$L$is smaller than the order of$2^{(K-2)(K-3)}$, it decays at most like$1/\sqrt [{4}]{L}$.

This paper shows that the Hirschfeld-Gebelein- Rényi maximal correlation between the message and the ciphertext provides good secrecy guarantees for cryptosystems that use short keys. We first establish a bound on the eavesdropper's advantage in guessing functions of the message in terms of maximal correlation and the Rényi entropy of the message. This result implies that the maximal correlation is stronger than the notion of entropic security introduced by Russell and Wang. We then show that a small maximal correlation ρ can be achieved via a randomly generated cipher with key length ≈ 2 log(1/ρ), independent of the message length, and by a stream cipher with key length 2 log(1/ρ) + logn + 2 for a message of length n. We establish a converse showing that these ciphers are close to optimal. This is in contrast with the entropic security for which there is a gap between the lower and upper bounds. Finally, we show that a small maximal correlation implies secrecy with respect to several mutual information-based criteria but is not necessarily implied by them. Hence, maximal correlation is a stronger and more practically relevant measure of secrecy than the mutual information.

Existing fixed-length feedback communication schemes are either specialized to particular channels (Schalkwijk-Kailath, Horstein), or apply to general channels but either have high coding complexity (block feedback schemes) or are difficult to analyze (posterior matching). This paper introduces a new fixed-length feedback coding scheme which achieves the capacity for all discrete memoryless channels, has an error exponent that approaches the sphere packing bound as the rate approaches the capacity, and has O(n log n) coding complexity. These benefits are achieved by judiciously combining features from previous schemes with new randomization technique and encoding/decoding rule. These new features make the analysis of the error probability for the new scheme easier than for posterior matching.

This paper introduces the notion of exact common information, which is the minimum description length of the common randomness needed for the exact distributed generation of two correlated random variables (X, Y). We introduce the quantity G(X; Y) = minX→W→YH(W) as a natural bound on the exact common information and study its properties and computation. We then introduce the exact common information rate, which is the minimum description rate of the common randomness for the exact generation of a 2-DMS (X, Y). We give a multiletter characterization for it as the limit Ḡ(X; Y) = limn→∞(1/n)G(Xn; Yn). While in general Ḡ(X; Y) is greater than or equal to the Wyner common information, we show that they are equal for the Symmetric Binary Erasure Source. We do not know, however, if the exact common information rate has a single letter characterization in general.

Existing feedback communication schemes are either specialized to particular channels (Schalkwijk-Kailath, Horstein), apply to general channels but have high coding complexity (block feedback schemes), or are difficult to analyze (posterior matching). This paper introduces a feedback coding scheme that achieves the capacity for all discrete memoryless channels with a bound on the error exponent that approaches the sphere packing bound as the rate approaches the capacity and coding complexity of only O(n log n). These benefits are attained by combining features from previous schemes with new randomization technique and decoding rule.

In this paper, we consider vector space interference alignment strategies over the K-user interference channel and derive an upper bound on the achievable degrees of freedom as a function of the channel diversity L. The channel diversity L is modeled by L independently fading real-valued parallel channels. Existing results in the literature for K = 3 show that the optimal 1/2 degrees of freedom per user can be approached at the speed of 1/L (i.e. the gap to 1/2 degrees of freedom per user decreases inversely proportional to L). In this paper, we show that when K ≥ 4, the speed of convergence is significantly slower. In particular, the gap to 1/2 degrees of freedom per user can decrease at most like 1/√L. Furthermore, when K is of the order of √logL, the speed of convergence is smaller than 1√(L)4.

We investigate the data transmission problem in which a sequence of data is broadcast to a number of receivers via erasure channels with different erasure probabilities. Accordingly, the receivers wish to decode the data sequentially at different rates. We present a formulation of the problem and propose an optimal coding scheme. Our results can be employed in the streaming of a video clip by broadcasting, so that receivers with different bandwidths can play the video at different speeds. Specifically, receivers with sufficiently large bandwidth can play the video at normal speed, while others can play the video with pauses, or at a slower speed using time-scale modification. Our results completely characterize the fundamental tradeoff between the available bandwidth and the playback speed of the video.

This paper presents a relaxation of an assumption usually imposed in the recovery of sparse vectors with random support in pairs of orthonormal bases or incoherent dictionaries by basis pursuit. The assumption requires the phases of the entries of the sparse vector to be chosen randomly in [0, 2π). This paper provides probabilistic recovery guarantees for deterministic phases. We prove that, if a phase pattern is fixed, then a sparse vector with random support and corresponding phases can be recovered with high probability. As a result, the phases can take any distribution and can be dependent, as long as they are independent of the support. Furthermore, this improvement does not come at the expense of the maximum recoverable sparsity.