In some rate-distortion-type problems, the required fidelity of information is affected by past actions. As a result, the distortion function depends not only on the instantaneous distortion between a source symbol and its representation symbol, but also on past representations. In this paper, we give a formal definition of this problem and introduce both inner (achievable) and outer bounds on the rate-distortion tradeoff. We also discuss convexification of the problem, which makes it easier to find bounds. Problems of this type arise in biological information processing, as well as in recommendation engines; we provide an example applied to a simplified biological information processing problem.

We introduce a two-parameter family of discrepancy measures, termed \emph{$(G,f)$-divergences}, obtained by applying a non-decreasing function $G$ to an $f$-divergence $D_f$. Building on Csiszár's formulation of mutual $f$-information, we define a corresponding $(G,f)$-information measure $ I_{G,f}(X;Y)$. A central theme of the paper is subadditivity over product distributions and product channels. We develop reduction principles showing that, for broad classes of $G$, it suffices to verify divergence subadditivity on binary alphabets. Specializing to the functions $G(x)\in\{x,\log(1+x),-\log(1-x)\}$, we derive tractable sufficient conditions on $f$ that guarantee subadditivity, covering many standard $f$-divergences. Finally, we present applications to finite-blocklength converses for channel coding, bounds in binary hypothesis testing, and an extension of the Shannon--Gallager--Berlekamp sphere-packing exponent framework to subadditive $(G,f)$-divergences.

We introduce a new variant of variable-length source coding for sending a source over two parallel channels, one of which is costly and the other free. We give a complete solution to this problem. Next, we relate the problem to the number partitioning problem, which is the task of dividing a given list of numbers into a pre-specified number of subsets such that the sum of the numbers in each subset is as nearly equal as possible. We introduce two new objective functions for this problem and show that an adapted version of the Huffman coding algorithm (with a runtime of $\mathcal{O}(n \log n)$ for input size $n$) produces the optimal solution for one objective function, and a nearly optimal solution for the other objective function.

We compute the capacity region of a sum of broadcast channels whose components are degraded, less-noisy, more-capable, deterministic, or semi-deterministic. We achieve this by showing that an auxiliary-receiver outer bound, previously introduced by some of the authors, matches Marton's inner bound. This result generalizes a previously known result for the sum of two reversely degraded broadcast channels due to El Gamal (1980). Moreover, we define a class of primary broadcast channels and show an analogous result for the sum of primary broadcast channels.

We study the hypercontractivity ribbon and the $Φ$-ribbon for joint distributions that obey a given independence structure, obtaining tight bounds in some basic regimes. For general independence structures, modeled as a hypergraph whose hyperedges specify mutually independent subcollections of random variables, we provide an explicit inner bound on the $Φ$-ribbon described by a simple convex hull of incidence vectors. We also provide a new multipartite generalization version and a $Φ$-mutual information analogue of the Zhang--Yeung inequality, which implies nontrivial points in the hypercontractivity ribbon and the $Φ$-ribbon respectively. Finally, we propose the matrix $Φ$-ribbon based on matrix $Φ$-entropy and establish the tensorization and data processing properties, together with the calculation of an exact matrix SDPI constant for the doubly symmetric binary source.

A source encoder is stable if a small change in the source sequence (e.g., changing a few symbols) results in a small (or bounded) change in the output codeword. By this definition, the common technique of random binning is unstable; because the mapping is random, two nearly identical source sequences can be assigned to completely unrelated bin indices. We study compression rates of stable lossless source codes. Using combinatorial arguments, we derive information-theoretic limits on the achievable rate as a function of the stability parameters.

We consider the source model key agreement problem involving two legitimate parties and an eavesdropper who observe n i.i.d. samples of X, Y, and Z, respectively. In this paper, we focus on one of the simplest instances where the key capacity remains open, specifically when X and Y are binary random variables and Z is a function of the pair (X, Y). The best-known upper bound on the key capacity is characterized by an inf-max optimization problem that generally lacks a closed-form solution. We provide general conditions under which the upper bound reduces to I(X;Y). As an example, we consider the XOR setting in which X and Y are binary, and Z is the XOR of X and Y. The upper bound reduces to I(X;Y) for this source. Next, we conjecture that the rate I(X;Y) is not achievable for the XOR source and provide some ideas that might be useful for developing a new upper bound on the source model problem.

We consider the source model key agreement problem involving two legitimate parties and an eavesdropper who observe n i.i.d. samples of X and Y and Z respectively. In this paper, we focus on one of the simplest instances where the key capacity remains open, specifically when X and Y are binary random variables and Z is a function of the pair ($X, Y$). The best-known upper bound on the key capacity is characterized by an inf-max optimization problem that generally lacks a closedform solution. In this paper, we solve the optimization for some class of sources, thereby providing simple expressions for the upper bound. We provide general conditions under which the upper bound reduces to$I(X; Y)$. As an example, we consider the XOR setting in which X and Y are binary, and Z is the XOR of X and Y. The upper bound reduces to$I(X; Y)$for this source. Next, we conjecture that the rate$I(X; Y)$is not achievable for the XOR source, and provide some ideas that might be useful for developing a new upper bound.${ }^{1}$

We study the most-informative Boolean function conjecture using a differential equation approach. This leads to a formulation of a functional inequality on finite-dimensional random variables. We also develop a similar inequality in the case of the Hellinger conjecture. Finally, we conjecture a specific finite-dimensional inequality that, if proved, will lead to a proof of the Boolean function conjecture in the balanced case. We further show that the above inequality holds modulo four explicit inequalities (all of which seem to hold via numerical simulation), with the first three containing just two variables and a final one involving four variables.

We study Marton's inner bound for a general two-receiver discrete memoryless broadcast channel. We conjecture a structural result on the optimizers of Marton's inner bound, which, if true, would greatly simplify the evaluation of the bound and provide new insights into the underlying optimization problem. We derive an equivalent characterization for the sum-rate that demonstrates a similar decoupling as one suggested by the conjecture.

This paper employs the add-and-subtract technique of the auxiliary receiver approach to establish a new upper bound for the distributed hypothesis testing problem. This new bound has fewer assumptions than the upper bound proposed by Rahman and Wagner, is at least as tight as the bound by Rahman and Wagner, and can outperform it in certain Gaussian settings. Conceptually speaking, unlike Rahman and Wagner, who view their additional receiver as side information, we view it as an auxiliary receiver and use a different manipulation for singleletterization.11This work was supported by the CUHK Direct Grant 4055193.

Diffusion models have demonstrated remarkable success in high-fidelity image synthesis and prompt-guided generative modeling. However, ensuring adequate diversity in generated samples of prompt-guided diffusion models remains a challenge, particularly when the prompts span a broad semantic spectrum and the diversity of generated data needs to be evaluated in a prompt-aware fashion across semantically similar prompts. Recent methods have introduced guidance via diversity measures to encourage more varied generations. In this work, we extend the diversity measure-based approaches by proposing the *S*calable *P*rompt-*A*ware *R*eny *K*ernel *E*ntropy Diversity Guidance (*SPARKE*) method for prompt-aware diversity guidance. SPARKE utilizes conditional entropy for diversity guidance, which dynamically conditions diversity measurement on similar prompts and enables prompt-aware diversity control. While the entropy-based guidance approach enhances prompt-aware diversity, its reliance on the matrix-based entropy scores poses computational challenges in large-scale generation settings. To address this, we focus on the special case of \textit{Conditional latent RKE Score Guidance}, reducing entropy computation and gradient-based optimization complexity from the $\mathcal{O}(n^3)$ of general entropy measures to $\mathcal{O}(n)$. The reduced computational complexity allows for diversity-guided sampling over potentially thousands of generation rounds on different prompts. We numerically test the SPARKE method on several text-to-image diffusion models, demonstrating that the proposed method improves the prompt-aware diversity of the generated data without incurring significant computational costs. We release our code on the project page: [https://mjalali.github.io/SPARKE/](https://mjalali.github.io/SPARKE).

In this paper, we establish a new outer bound to the capacity region of the Gaussian Z-interference channel and also characterize the capacity of two new classes of discrete memory less interference channels. The latter is achieved by proving the optimality of the Han-Kobayashi in-ner bound via traditional converse proofs. The former is done by utilizing an outer bound, generally not computable for discrete interference channels, to derive a new outer bound for Gaussian Z-interference channels, and its computability is deduced by showing Gaussian extremality.1

We define the “relative” fractional independence number of a graph$G$with respect to another graph$H$, as where the maximum is taken over all graphs$W$.,$G \boxtimes W$is the strong product of$G$and$W$, and$\alpha$denotes the independence number. We give a nontrivial linear program to compute$\alpha^{*}(G\vert H)$, and discuss some of its properties. We show that$\alpha^{*}(G\vert H) \geq \frac{X(G)}{X(H)}\geq-\frac{1}{\alpha^{*}(H\vert G)}$, where$X(G)$can be the independence number, the Shannon capacity, the fractional independence number, the Lovász number, or the Schrijver's or Szegedy's variants of the Lovász number of a graph$G$, This inequality is the first explicit nontrivial upper bound on the ratio of the invariants of two arbitrary graphs, as mentioned earlier, which can also be used to obtain upper or lower bounds for these invariants. As explicit applications, we present new upper bounds for the ratio of the Shannon capacity of two Cayley graphs and compute new lower bounds on the Shannon capacity of certain Johnson graphs (yielding the exact value of their Haemers number). Moreover, we show that$\alpha^{*}(G\vert H)$can be used to present a stronger version of the well-known No-Homomorphism Lemma.

Fair supervised learning algorithms assigning labels with little dependence on a sensitive attribute have attracted great attention in the machine learning community. While the demographic parity (DP) notion has been frequently used to measure a model’s fairness in training fair classifiers, several studies in the literature suggest potential impacts of enforcing DP in fair learning algorithms. In this work, we analytically study the effect of standard DP-based regularization methods on the conditional distribution of the predicted label given the sensitive attribute. Our analysis shows that an imbalanced training dataset with a non-uniform distribution of the sensitive attribute could lead to a classification rule biased toward the sensitive attribute outcome holding the majority of training data. To control such inductive biases in DP-based fair learning, we propose a sensitive attribute-based distributionally robust optimization (SA-DRO) method improving robustness against the marginal distribution of the sensitive attribute. Finally, we present several numerical results on the application of DP-based learning methods to standard centralized and distributed learning problems. The empirical findings support our theoretical results on the inductive biases in DP-based fair learning algorithms and the debiasing effects of the proposed SA-DRO method. The project code is available at [github.com/lh218/Fairness-IB.git](https://github.com/lh218/Fairness-IB.git).

We establish the noiseberg conjecture regarding the Han-Kobayashi region of the Gaussian Z-Interference channel with Gaussian signaling. We also provide a refined conjecture for the optimality of the HK inner bound with Gaussian signaling.

An upper bound is derived on the secret key rates of a general multiterminal wiretap channel. The bound unifies and generalizes some of the previously known bounds. Additionally, a multivariate dependence balance bound is introduced that is of independent interest.

In this paper, we provide three applications for$ {\mathsf {f}}$-divergences: (i) we introduce Sanov’s upper bound on the tail probability of the sum of independent random variables based on super-modular$ {\mathsf {f}}$-divergence and show that our generalized Sanov’s bound strictly improves over ordinary one, (ii) we consider the lossy compression problem which studies the set of achievable rates for a given distortion and code length. We extend the rate-distortion function using mutual$ {\mathsf {f}}$-information and provide new and strictly better bounds on achievable rates in the finite blocklength regime using super-modular$ {\mathsf {f}}$-divergences, and (iii) we provide a connection between the generalization error of algorithms with bounded input/output mutual$ {\mathsf {f}}$-information and a generalized rate-distortion problem. This connection allows us to bound the generalization error of learning algorithms using lower bounds on the$ {\mathsf {f}}$-rate -distortion function. Our bound is based on a new lower bound on the rate-distortion function that (for some examples) strictly improves over previously best-known bounds.

Understanding generalization in modern machine learning settings has been one of the major challenges in statistical learning theory. In this context, recent years have witnessed the development of various generalization bounds suggesting different complexity notions such as the mutual information between the data sample and the algorithm output, compressibility of the hypothesis space, and the fractal dimension of the hypothesis space. While these bounds have illuminated the problem at hand from different angles, their suggested complexity notions might appear seemingly unrelated, thereby restricting their high-level impact. In this study, we prove novel generalization bounds through the lens of rate-distortion theory, and explicitly relate the concepts of mutual information, compressibility, and fractal dimensions in a single mathematical framework. Our approach consists of (i) defining a generalized notion of compressibility by using source coding concepts, and (ii) showing that the ’compression error rate’ can be linked to the generalization error both in expectation and with high probability. We show that in the ’lossless compression’ setting, we recover and improve existing mutual information-based bounds, whereas a ’lossy compression’ scheme allows us to link generalization to the rate-distortion dimension - a particular notion of fractal dimension. Our results bring a more unified perspective on generalization and open up several future research directions.

We develop a new upper bound on the capacity of the relay channel that is tighter than previously known upper bounds. This upper bound is proved using traditional weak converse techniques involving mutual information inequalities and Gallager-type explicit identification of auxiliary random variables. We show that the new upper bound is strictly tighter than all previous bounds for the Gaussian relay channel with non-zero channel gains. When specialized to the relay channel with orthogonal receiver components, the bound resolves a conjecture by Kim on a class of deterministic relay channels. When further specialized to the class of product-form relay channels with orthogonal receiver components, the bound resolves a generalized version of Cover’s relay channel problem, recovers the recent upper bound for the Gaussian case by Wuet al., and improves upon the recent bounds for the binary symmetric case by Wuet al.and Barneset al., which were obtained using non-traditional geometric proof techniques. For the special class of a relay channel with orthogonal receiver components, we develop another upper bound on the capacity which utilizes an auxiliary receiver and show that it is strictly tighter than the bound by Tandon and Ulukus. Finally, we show through the Gaussian relay channel with i.i.d. relay output sequence that the bound with the auxiliary receiver can be strictly tighter than our main bound.

This paper employs auxiliary receivers as a mathematical tool to identify Gallager-type auxiliary random variables and write outer bounds for some basic multiuser settings. This approach is then applied to the relay, interference, and broadcast channel settings, yielding new outer bounds that improve on existing outer bounds and strictly outperform classical outer bounds. For instance, we strictly improve on: the cutset outer bound for the scalar Gaussian relay channel, the outer bounds for the Gaussian Z-interference channel, and the outer bounds for the two receiver broadcast channel.

We establish a new upper bound on the capacity of the relay channel which is tighter than all previous bounds. The upper bound uses traditional weak converse techniques involving mutual information inequalities and identification of auxiliary random variables via past and future channel random variable sequences. We show that the new bound is strictly tighter than all previous bounds for the Gaussian relay channel for every set of non-zero channel gains. When specialized to the class of relay channels with orthogonal receiver components, the bound resolves a conjecture by Kim on a class of deterministic relay channels. When further specialized to the class of product-form relay channels with orthogonal receiver components, the bound resolves a generalized version of Cover's relay channel problem, recovers the recent upper bound for the Gaussian case by Wu et al. and also improves upon the recent bounds for the binary symmetric case by Wu et al. and Barnes et al., which were all obtained using non-traditional geometric proof techniques.

We establish an information inequality that is motivated by the capacity region computation for the Gaussian Z-interference channel. This yields an improved slope for the capacity region at Costa's corner point. We believe the inequality may also be of independent interest as it provides a non-trivial upper bound on the entropy of sums of independent random variables.

We study learning algorithms when there is a mismatch between the distributions of the training and test datasets of a learning algorithm. The effect of this mismatch on the generalization error and model misspecification are quantified. Moreover, we provide a connection between the generalization error and the rate-distortion theory, which allows one to utilize bounds from the rate-distortion theory to derive new bounds on the generalization error and vice versa. In particular, the rate-distortion-based bound strictly improves over the earlier bound by Xu and Raginsky even when there is no mismatch. We also discuss how “auxiliary loss functions” can be utilized to obtain upper bounds on the generalization error. A full version of this paper is accessible at [1].

This paper studies lower bounds on the capacity of the relay channel with orthogonal receiver components (also referred to as primitive relay channel). We show that the lower bound in Theorem 7 of Cover and El Gamal, which uses mixed decode-forward and compress-forward strategies, is identical to the lower bound of Chong, Motani and Garg, and is always larger than or equal to the recent lower bound of Mondelli, Hassani and Urbanke. We provide a simplified expression for the lower bound in Theorem 7 of Cover and El Gamal and interpret one of its auxiliary variables as implementing the randomized time-sharing strategy. Next, we compare the lower bound for the Gaussian relay channel with orthogonal receiver components to existing upper bounds. Finally, we disprove a conjecture by Ahlswede and Han on the capacity of the subclass of relay channels with orthogonal receiver components and i.i.d. output. A full version of this paper is accessible at: http://chandra.ie.cuhk.edu.hk/pub/papers/NIT/Prim-Rel-LB.pdf

One of the main challenges in diffusion-based molecular communication is dealing with the non-linearity of reaction-diffusion chemical equations. While numerical methods can be used to solve these equations, a change in the input signals or the parameters of the medium requires one to redo the simulations. This makes it difficult to design modulation schemes and practically impossible to prove the optimality of a given transmission strategy. In this paper, we provide an analytical technique for modeling the non-linearity of chemical reaction equations based on the perturbation method. The perturbation method expresses the solution in terms of an infinite power series. An approximate solution can be found by keeping the leading terms of the power series. The approximate solution is shown to track the true solution if either the simulation time interval or the reaction rate is sufficiently small. Approximate solutions for long time intervals are also discussed. An illustrative example is given. For this example, it is shown that when the reaction rate (or the total time interval) is low, instead of using a continuous release waveform, it is optimal for the transmitters to release molecules at two time instances.

One of the main challenges in diffusion-based molecular communication is dealing with the non-linearity of reaction diffusion chemical equations. While numerical methods can be used to solve these equations, a change in the input signals or in the parameters of the medium requires one to redo the simulations. This makes it difficult to design modulation schemes and practically impossible to prove the optimality of a given transmission strategy. We provide an analytical technique for modeling non-linearity of chemical reaction equations based on the perturbation method. It is shown that at low reaction rates, instead of using a continuous transmission waveform, it is optimal for each transmitter to release molecules in a sequence of spikes.

Two new outer bounds for the two-receiver broad- cast channel are presented, both of which strictly improve on the current best known bound. The key idea is to employ an auxiliary receiver as a mathematical tool to write the bounds. This idea is then applied to obtain bounds for the relay and interference channels as well, which also improve on the current best-known bounds for some situations.

A coding scheme for transmission of a bit maps a given bit to a sequence of channel inputs (called the codeword associated to the transmitted bit). In this paper, we study the problem of designing the best code for a discrete Poisson channel with memory (under peak-power and total-power constraints). The outputs of a discrete Poisson channel with memory are Poisson distributed random variables with a mean comprising a fixed additive noise and a linear combination of past input symbols. Assuming a maximum-likelihood (ML) decoder, we find the best codebook design by minimizing the error probability of the decoder over all codebooks. For the case of having only a total-power constraint, the optimal code structure is obtained provided that the blocklength is greater than the memory length of the channel. For the case of having only a peak-power constraint, the optimal code is derived for arbitrary memory and blocklength in the high-power regime. For the case of having both the peak-power and total-power constraints, the optimal code is derived for memoryless Poisson channels when both the totalpower and the peak-power bounds are large.

In this paper, we study the zero error capacity of the molecular delay channel when multiple molecule types are available at the transmitter. In the molecular delay channel, each transmitted molecule (of any type) is received by a delay of at most $k$ time slots. Depending on the number of molecules that the transmitter is allowed to release in each time slot, we consider the following three cases: (i) when the maximum number of the released molecules of each type in each time slot is restricted (ii) when the total number of the released molecules (regardless of their type) in each time slot is restricted, and (iii) when the transmitter can use only one molecule type (of its choice) in each time slot. We derive lower bounds on the zero-error capacity of the delay channel for each case, by proposing zero-error codes that are based on the results by Kovačević and Popovski. We also derive upper bounds on the zero-error capacity of the delay channel. In the first case, these bounds match and yield the exact capacity, while in the other two cases, the bounds are shown to be close numerically. Our numerical results show that as the number of available molecule types increases, the capacity of the system increases substantially, compared to using only one molecule type. Furthermore, it is shown that the lower and upper bounds on the zero-error capacity of the delay channel in the second case are generally close to the lower and upper bounds in the third case, respectively, indicating the closeness of the zero-error capacities of the two cases. This result enables one to design a simpler system by employing a high rate code that has only one molecule type in each slot (designed for the third case) in the channel of the second case, without much rate loss.

A two-party key agreement problem with public discussion, known as the source model problem, is considered. By relating key agreement to hypothesis testing, a new coding scheme is developed that yields a sufficient condition to achieve a positive secret-key (SK) rate in terms of Rényi divergence. The merits of this coding scheme are illustrated by applying it to an erasure model for Eve's side information and by deriving an upper bound on Eve's erasure probabilities for which the SK capacity is zero. This bound strictly improves on the best known single-letter lower bound on the SK capacity. Moreover, the bound is tight when Alice's or Bob's source is binary, which extends a previous result for a doubly symmetric binary source. The results motivate a new measure for the correlation between two random variables which is of independent interest.

In this paper, a new measure of correlation is introduced. This measure depends on a parameter α, and is defined in terms of vector-valued Lpnorms. The measure is within a constant of the exponential of α-Rényi mutual information, and reduces to the trace norm (total variation distance) for α = 1. We provide some properties and applications of this measure of correlation. In particular, we establish a bound on the secrecy exponent of the wiretap channel (under the total variation metric) in terms of the α-Rényi mutual information according to Csiszár's proposal.

The problem of finding the optimal node density for reconstructing a stochastic signal from its noisy samples in sensor networks is considered. The signal could be nonstationary and nonbandlimited. A weight is assigned to each location that indicates the relative importance of the signal at that location. It is shown that when the number of samples is very large, the optimal density of the samples at each location is proportional to the square root of the weight associated to that location.

Chemical reactions are a prominent feature of molecular communication systems, with no direct parallels in wireless communications. While chemical reactions may be used inside the transmitter nodes, receiver nodes, or the communication medium, we focus on its utility in the medium in this paper. Such chemical reactions can be used to perform computation over the medium as molecules diffuse and react with each other (physical-layer computation). We propose the use of chemical reactions for the following purposes: 1) to reduce signal-dependent observation noise of receivers by reducing the signal density; 2) to realize molecular physical-layer network coding (PNC) by performing the natural XOR operation inside the medium; and 3) to reduce the inter-symbol interference (ISI) of other transmitters by canceling out the remaining molecules from previous transmissions. To make the ideas formal, we consider an explicit two-way relaying example with a transparent receiver (which has a signal-dependent noise). The proposed ideas are used to define a modulation scheme (which we call the PNC scheme). We compare the PNC with a previously proposed scheme for this problem, where the XOR operation is performed at the relay node (using a molecular logic gate). We call the latter, the straightforward network coding (SNC). It is observed that in addition to the simplicity of the proposed PNC scheme, it outperforms the SNC scheme especially when we consider ISI.

Marton's inner bound is the best known achievable rate region for a general two-receiver discrete memoryless broadcast channel. In this paper, we establish improved bounds on the cardinalities of the auxiliary random variables appearing in this inner bound to the true rate region. We combine a perturbation technique, along with a representation using concave envelopes of information-theoretic functions that involve the use of auxiliary random variables, to achieve this improvement. The new cardinality bounds lead to a proof that a randomized-time-division strategy achieves every rate triple in Marton's region for binary input broadcast channels. This extends the result by Hajek and Pursley which showed that the Cover-van der Muelen region was exhausted by the randomized-time-division strategy.

In this paper, we introduce a new measure of correlation for bipartite quantum states. This measure depends on a parameter$\alpha $, and is defined in terms of vector-valued$\textit {L}_{\textit {p}}$-norms. The measure is within a constant of the exponential of$\alpha $-Rényi mutual information, and reduces to the trace norm (total variation distance) for$\alpha =1$. We will prove some decoupling type theorems in terms of this measure of correlation, and present some applications in privacy amplification as well as in bounding the random coding exponents. In particular, we establish a bound on the secrecy exponent of the wiretap channel (under the total variation metric) in terms of the$\alpha $-Rényi mutual information according toCsiszár’s proposal.

The two-party key agreement problem with public discussion, known as the source model problem, is considered for an erasure model for Eve's side information. By relating the key agreement problem to hypothesis testing, a new coding scheme is developed that yields an upper bound on the maximum erasure probability for which the secret-key (SK) capacity is zero. The bound is shown to be tight when Alice's or Bob's source is binary, and this shows that the new code achieves larger SK rates than the best known coding scheme. A full version of this paper with extensions to general models for Eve's side information is available in [1].

While ISI is a common issue in classical communications, it is more challenging and prominent in the context of molecular communication, because one cannot readily combat ISI with classical channel equalization techniques. This is due to the fact that transmitter can only release a positive amount of concentration of a specific molecule into the medium. Previous works have proposed use of chemical reactions to remove molecules from the environment, and to effectively simulate negative signals. However, the differential equation describing a diffusion-reaction process is non-linear. This precludes the possibility of using Fourier transform tools. In this paper, a solution for simulating negative signals based on the diffusion-reaction channel model is proposed. While the proposed solution does not exploit the full degrees of freedom available for signaling in a diffusion-reaction process, but its end-to-end system is a linear channel and amenable to Fourier transform analysis. Based on our solution, a modulation scheme and a precoder are introduced and shown to have a significant reduction in error probability compared with previous modulation schemes, such as concentration shift keying (CSK), pre-equalization, depleted-molecule shift keying (D-MoSK), and molecular concentration shift keying (MCSK). The effects of various imperfections (such as quantization error) on the communication system performance are studied.

A measure of correlation is said to have the tensorization property if it does not change when computed for i.i.d. copies. More precisely, a measure of correlation between two random variables X, Y denoted by p(X, Y), has the tensorization property if p(Xn, Yn) = p(X, Y) where (Xn, Yn) denotes n i.i.d. copies of (X, Y). Two well-known examples of such measures are the maximal correlation and the hypercontractivity ribbon (HC ribbon). We show that the maximal correlation and the HC ribbon are special cases of the new notion of Φ-ribbons, defined in this paper for a class of convex functions Φ. Φ-ribbon reduces to the HC ribbon and the maximal correlation for special choices of Φ, and is a measure of correlation with the tensorization property. We show that the Φ-ribbon also characterizes the recently introduced Φ-strong data processing inequality constant. We further study the Φ-ribbon for the choice of Φ(t) = t2and introduce an equivalent characterization of this ribbon.

The sparsity and compressibility of finite-dimensional signals are of great interest in fields, such as compressed sensing. The notion of compressibility is also extended to infinite sequences of independent identically distributed or ergodic random variables based on the observed error in their nonlinear k-term approximation. In this paper, we use the entropy measure to study the compressibility of continuous-domain innovation processes (alternatively known as white noise). Specifically, we define such a measure as the entropy limit of the doubly quantized (time and amplitude) process. This provides a tool to compare the compressibility of various innovation processes. It also allows us to identify an analogue of the concept of “entropy dimension" which was originally defined by Rényi for random variables. Particular attention is given to stable and impulsive Poisson innovation processes. Here, our results recognize Poisson innovations as the more compressible ones with an entropy measure far below that of stable innovations. While this result departs from the previous knowledge regarding the compressibility of impulsive Poisson laws compared with continuous fat-tailed distributions, our entropy measure ranks α-stable innovations according to their tail.

In some applications, the variance of additive measurement noise depends on the signal that we aim to measure. For instance, additive signal-dependent Gaussian noise (ASDGN) channel models are used in molecular and optical communication. Herein, we provide lower and upper bounds on the capacity of additive signal-dependent noise (ASDN) channels. The first lower bound is based on an extension of majorization inequalities, and the second lower bound utilizes the properties of the differential entropy. The lower bounds are valid for arbitrary ASDN channels. The upper bound is based on a previous idea of the authors (“symmetric relative entropy”) and is applied to the ASDGN channels. These bounds indicate that in the ASDN channels (unlike the classical additive white Gaussian noise channels), the capacity does not necessarily become larger by reducing the noise variance function. We also provide sufficient conditions under which the capacity becomes infinite. This is complemented by some conditions implying that the capacity is finite, and a unique capacity achieving measure exists (in the sense of the output measure).

In this paper, we consider a secure network coding problem in which some secret keys are shared among legitimate nodes, and there exists an eavesdropper which is able to hear a subset of links. We show the equivalency of secure network coding under weak and strong secrecy conditions. For linear network coding, we show a stronger result: equivalency of "perfect secrecy and zero-error constraints" to "weak secrecy and $epsilon$-error constraints". This is a secure version of the result obtained by Langberg and Effros, on the equivalence of zero-error and $epsilon$-error regions in the network coding problem with co-located sources. Jalali and Ho exploit extractor functions to prove the weak and strong rate region equivalency for this network; however, to prove this equivalency, we develop some tools in random binning and prove the equivalency in a slightly more general setting.

A Santha--Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani show that deterministic randomness extraction from these sources is impossible. In this paper, we study the generalization of SV sources for nonbinary sequences. We show that unlike the binary setup of Santha and Vazirani, deterministic randomness extraction in the generalized case is sometimes possible. In particular, if the adversary has access to $s$ “nondegenerate” dice that are $c$-sided and can choose one die to throw based on the previous realizations of the dice, then deterministic randomness extraction is possible if $s

Theorem 5 of A. Gohari, V. Anantharam,IEEE Transactions on Information Theory, vol. 56, no. 8, pp. 3973-3996, 2010, states an upper bound on the secrecy capacity for the source model problem. It has a three page proof given in Appendix B of the paper. Unfortunately, we show that this bound does not provide any improvement over the simpler bound given in Corollary 1 of the paper. We also provide an example of a family of two agent source model problems where the one-way secrecy rate in each direction is zero, but the secrecy rate is nonzero and can be determined exactly as a conditional mutual information.

In this paper, we study the problem of simulating a discrete memoryless channel (DMC) from another DMC under an average-case and an exact model. We present several achievability and infeasibility results, with tight characterizations in special cases. In particular, for the exact model, we fully characterize when a binary symmetric channel can be simulated from a binary erasure channel when there is no shared randomness. We also provide infeasibility and achievability results for the simulation of a binary channel from another binary channel in the case of no shared randomness. To do this, we use the properties of Rényi capacity of a given order. We also introduce a notion of “channel diameter” which is shown to be additive and satisfy a data processing inequality.

In this paper, we investigate the index coding problem in the presence of an eavesdropper. Messages are to be sent from one transmitter to a number of legitimate receivers who have side information about the messages, and share a set of secret keys with the transmitter. To do this, the transmitter communicates to the legitimate receivers the public code C, which is also heard by the eavesdropper. We assume perfect secrecy, meaning that the eavesdropper should not be able to retrieve any information about the message set from the public communication. We study the minimum key lengths for zero-error and perfectly secure index coding problem. On one hand, this problem is a generalization of the index coding problem (and thus a difficult one). On the other hand, it is a generalization of the Shannon's cipher system. We show that a generalization of Shannon's one-time pad strategy is optimal up to a multiplicative constant, meaning that it obtains the entire boundary of the cone formed by looking at the secure rate region from the origin. This shows the optimality of the generalized one-time pad for minimizing the consumption of shared secret keys per message bits, when public communication is free (the transmitter is not charged for the rate of the public communication). Finally, we consider relaxation of the perfect secrecy and zero-error constraints to weak secrecy and asymptotically vanishing probability of error, and provide a secure version of the result, obtained by Langberg and Effros, on the equivalence of zero-error and ε-error regions in the conventional index coding problem.

We introduce a “high-probability” framework for repeated games with incomplete information. In our non-equilibrium setting, players aim to guarantee a certain payoff with high probability, rather than in expected value. We provide a high-probability counterpart of the classical result of Mertens and Zamir for the zero-sum repeated games. Any payoff that can be guaranteed with high probability can be guaranteed in expectation, but the reverse is not true. Hence, unlike the average payoff case where the payoff guaranteed by each player is the negative of the payoff by the other player, the two guaranteed payoffs would differ in the high-probability framework. One motivation for this framework comes from information transmission systems, where it is customary to formulate problems in terms of asymptotically vanishing probability of error. Finally, we introduce compound arbitrarily varying channels, and use the high-probability framework to study this problem.

In this paper, a simple memory limited transmitter for molecular communication is proposed, in which information is encoded in the emission rate of the molecules. Taking advantage of memory, the proposed transmitter reduces the ISI problem by properly adjusting its emission rate, which can be interpreted as water-filling on the expected interference. The error probability of the proposed scheme is derived and the result is compared with the error probability of the optimal transmitter obtained by dynamic programming methods. Furthermore, for the special case of channel with one symbol memory, a tight lower bound on error probability is derived. Numerical results show that the performance of introduced transmitter is near optimal. Simplicity is the key feature of the presented communication system: the transmitter follows a simple rule, the receiver is a simple threshold decoder, and only one type of molecule is used to convey the information.

The LTI-Poisson model is a natural extension of the conventional memoryless Poisson channel to include memory, and can model the ISI effect in diffusion based molecular communication networks. In this paper, we exploit prior art on linear ISI channels to provide a computable finite-letter characterization of the capacity of single-hop LTI-Poisson networks. Then we find more explicit single-letter lower and upper bounds on the capacity in the point to point case. Further, an approach for bounding mutual information in the low SNR regime using the symmetrized KL divergence is introduced and its applicability for Poisson channels is demonstrated. This leads to a non-trivial upper bound on the capacity of Poisson channel with a maximum transmission constraint in the low SNR regime, which to best of our knowledge is the first such bound.

In this paper, a simple memory limited transmitter for molecular communication is proposed, in which information is encoded in the diffusion rate of the molecules. Taking advantage of memory, the proposed transmitter reduces the ISI problem by properly adjusting its diffusion rate. The error probability of the proposed scheme is derived and the result is compared with the lower bound on error probability of the optimum transmitter. It is shown that the performance of introduced transmitter is near optimal (under certain simplifications). Simplicity is the key feature of the presented communication system: the transmitter follows a simple rule, the receiver is a simple threshold decoder and only one type of molecule is used to convey the information.

A function is said to be additive if, similar to mutual information, expands by a factor of n, when evaluated on n i.i.d. repetitions of a source or channel. On the other hand, a function is said to satisfy the tensorization property if it remains unchanged when evaluated on i.i.d. repetitions. Additive rate regions are of fundamental importance in network information theory, serving as capacity regions or upper bounds thereof. Tensorizing measures of correlation have also found applications in distributed source and channel coding problems as well as the distribution simulation problem. Prior to our work only two measures of correlation, namely the hypercontractivity ribbon and maximal correlation (and their derivatives), were known to have the tensorization property. In this paper, we provide a general framework to obtain a region with the tensorization property from any additive rate region. We observe that hypercontractivity ribbon indeed comes from the dual of the rate region of the Gray-Wyner source coding problem, and generalize it to the multipartite case. Then we define other measures of correlation with similar properties from other source coding problems.

In this paper, we investigate the index coding problem in the presence of an eavesdropper. Messages are to be sent from one transmitter to a number of legitimate receivers who have side information about the messages, and share a set of secret keys with the transmitter. We assume perfect secrecy, meaning that the eavesdropper should not be able to retrieve any information about the message set. This problem is a generalization of the Shannon's cipher system. We study the minimum key lengths for zero-error and perfectly secure index coding problems.

Non-locality is the phenomenon of observing strong correlations among the outcomes of local measurements of a multipartite physical system. No-signaling boxes are the abstract objects for studying non-locality, and wirings are local operations on the space of no-signaling boxes. This means that, no matter how non-local the nature is, the set of physical non-local correlations must be closed under wirings. Then, one approach to identify the non-locality of nature is to characterize the closed sets of non-local correlations. Although non-trivial examples of wirings of no-signaling boxes are known, there is no systematic way to study wirings. In particular, given a set of no-signaling boxes, we do not know a general method to prove that it is closed under wirings. In this paper, we propose the first general method to construct such closed sets of non-local correlations. We show that a well-known measure of correlation, called maximal correlation, when appropriately defined for non-local correlations, is monotonically decreasing under wirings. This establishes a conjecture about the impossibility of simulating isotropic boxes from each other, implying the existence of a continuum of closed sets of non-local boxes under wirings. To prove our main result, we introduce some mathematical tools that may be of independent interest: we define a notion of maximal correlation ribbon as a generalization of maximal correlation, and provide a connection between it and a known object called hypercontractivity ribbon; we show that these two ribbons are monotone under wirings too.

In this paper, we study the problem of channel simulation via interactive communication, known as the coordination capacity, in a two-terminal network. We assume that two terminals observe independent identically distributed (i.i.d.) copies of two random variables and would like to generate i.i.d. copies of two other random variables jointly distributed with the observed random variables. The terminals are provided with two-way communication links, and shared common randomness, all at limited rates. Two special cases of this problem are the interactive function computation studied by Ma and Ishwar, and the tradeoff curve between one-way communication and shared randomness studied by Cuff. The latter work had inspired Gohari and Anantharam to study the general problem of channel simulation via interactive communication stated above. However, only inner and outer bounds for the special case of no shared randomness were obtained in their work. In this paper, we settle this problem by providing an exact computable characterization of the multiround problem. To show this we employ the technique of output statistics of random binning that has been recently developed by the authors.

In this paper we provide the correct tight constant to a data-processing inequality claimed by Erkip and Cover. The correct constant turns out to be a particular hypercontractivity parameter of (X,Y), rather than their squared maximal correlation. We also provide alternate geometric characterizations for both maximal correlation as well as the hypercontractivity parameter that characterizes the data-processing inequality.

In this paper we define critical graphs as minimal graphs that support a given set of rates for the index coding problem, and study them for both the one-shot and asymptotic setups. For the case of equal rates, we find the critical graph with minimum number of edges for both one-shot and asymptotic cases. For the general case of possibly distinct rates, we show that for one-shot and asymptotic linear index coding, as well as asymptotic non-linear index coding, each critical graph is a union of disjoint strongly connected subgraphs (USCS). On the other hand, we identify a non-USCS critical graph for a one-shot non-linear index coding problem. In addition, we show that the capacity region of the index coding associated with a given graph can be obtained by time-sharing over valid index codes for its strongly connected components.

In this paper, a diffusion-based molecular communication channel between two nano-machines is considered. The effect of the amount of memory on performance is characterized, and a simple memory-limited decoder is proposed; its performance is shown to be close to that of the best possible decoder (without any restrictions on the computational complexity or its functional form), using genie-aided upper bounds. This effect is adapted to the case of Molecular Concentration Shift Keying; it is shown that a four-bit memory achieves nearly the same performance as infinite memory for all of the examples considered. A general class of threshold decoders is considered and shown to be suboptimal for a Poisson channel with memory, unless the SNR is higher than a computed threshold. During each symbol duration (symbol period), the probability that a released molecule hits the receiver changes over the duration of the period; thus, we also consider a receiver that samples at a rate higher than the transmission rate (a multi-read system). A multi-read system improves performance. The associated decision rule for this system is shown to be a weighted sum of the samples during each symbol interval. The performance of the system is analyzed using the saddle point approximation. The best performance gains are achieved for an oversampling factor of three for the examples considered.

Expressions of several capacity regions in quantum information theory involve an optimization over auxiliary quantum registers. Evaluating such expressions requires bounds on the dimension of the Hilbert space of these auxiliary registers, for which no nontrivial technique is known; we lack a quantum analog of the Carathéodory theorem. In this paper, we develop a new non-Carathéodory-type tool for evaluating expressions involving a single quantum auxiliary register and several classical random variables. As we show, such expressions appear in problems of entanglement-assisted Gray-Wyner and entanglement-assisted channel simulation, where the question of whether entanglement helps in these settings is related to that of evaluating expressions with a single quantum auxiliary register. To evaluate such expressions, we argue that developing a quantum analog of the Carathéodory theorem requires a better understanding of a notion which we call “quantum conditioning.” We then proceed by proving a few results about quantum conditioning, one of which is that quantum conditioning is strictly richer than the usual classical conditioning.

In this paper, we provide a simple framework for deriving one-shot achievable bounds for some problems in quantum information theory. Our framework is based on the joint convexity of the exponential of the collision relative entropy and is a (partial) quantum generalization of the technique of Yassaee et al. from classical information theory. Based on this framework, we derive one-shot achievable bounds for the problems of communication over classical-quantum channels, quantum hypothesis testing, and classical data compression with quantum side information. We argue that our one-shot achievable bounds are strong enough to give the asymptotic achievable rates of these problems even up to the second order.

Marton's inner bound is the tightest known inner bound on the capacity region of the broadcast channel. It is not known, however, if this bound is tight in general. One approach to settle this key open problem in network information theory is to investigate the multiletter extension of Marton's bound, which is known to be tight in general. This approach has become feasible only recently through the development of a new method for bounding cardinalities of auxiliary random variables by Gohari and Anantharam. This paper undertakes this long overdue approach to establish several new results, including 1) establishing the optimality of Marton's bound for new classes of product broadcast channels, 2) showing that the best-known outer bound by Nair and El Gamal is not tight in general, and 3) finding sufficient conditions for a global maximizer of Marton's bound that imply that the 2-letter extension does not increase the achievable rate. Motivated by the new capacity results, we establish a new outer bound on the capacity region of product broadcast channels.

In this paper, we revisit the structure of infeasibility results in network information theory, based on a notion of information state. We also discuss ideas for generalizing a known outer bound for lossless transmission of independent sources over a network to one of lossy transmission of dependent sources over the same network. To concretely demonstrate this, we apply our ideas and prove new results for lossy transmission of dependent sources by generalizing: 1) the cut-set bound; 2) the best known outer bound on the capacity region of a general broadcast channel; and 3) the outer bound part of the result of Maric, Yates, and Kramer on strong interference channels with a common message.

We establish several new results on Marton's inner bound on the capacity region of the general broadcast channel. Inspired by the fact that Marton's coding scheme without superposition coding is optimal in the Gaussian case, we consider the class of binary input degraded broadcast channels with no common message that have the same property. We characterize this class. We also establish new properties of Marton's inner bound that help restrict the search space for computing the Marton sum rate. In particular, we establish an extension of the XOR case of the binary inequality of Nair, Wang, and Geng.

This paper introduces a new and ubiquitous framework for establishing achievability results in network information theory problems. The framework uses random binning arguments and is based on a duality between channel and source coding problems. Furthermore, the framework uses pmf approximation arguments instead of counting and typicality. This allows for proving coordination and strong secrecy problems, where certain statistical conditions on the distribution of random variables need to be satisfied. These statistical conditions include independence between messages and eavesdropper's observations in secrecy problems and closeness to a certain distribution (usually, i.i.d. distribution) in coordination problems. One important feature of the framework is to enable one to add an eavesdropper and obtain a result on the secrecy rates for free. We make a case for generality of the framework by studying examples in a variety of settings including channel coding, lossy source coding, joint source-channel coding, coordination, strong secrecy, feedback, and relaying. In particular, by investigating the framework for the lossy source coding problem over broadcast channel, it is shown that the new framework provides a simple alternative scheme to the hybrid coding scheme. In addition, new results on secrecy rate region (under strong secrecy criterion) of wiretap broadcast channel and wiretap relay channel are derived. In a set of accompanied papers, we have shown the usefulness of the framework to establish achievability results for coordination problems, including interactive channel simulation, coordination via relay and channel simulation via another channel.

Marton's region is the best known inner bound for a general discrete memoryless broadcast channel. We establish improved bounds on the cardinalities of the auxiliary random variables. We combine the perturbation technique along with a representation using concave envelopes to achieve this improvement. As a corollary of this result, we show that a randomized time division strategy achieves the entire Marton's region for binary input broadcast channels, extending the previously known result for the sum-rate and validating a previous conjecture due to the same authors.

This paper proposes a novel technique to prove a one-shot version of achievability results in network information theory. The technique is not based on covering and packing lemmas. In this technique, we use a stochastic encoder and decoder with a particular structure for coding that resembles both the ML and the joint-typicality coders. Although stochastic encoders and decoders do not usually enhance the capacity region, their use simplifies the analysis. The Jensen inequality lies at the heart of error analysis, which enables us to deal with the expectation of many terms coming from stochastic encoders and decoders at once. The technique is illustrated via four examples: point-to-point channel coding, Gelfand-Pinsker, broadcast channel and Berger-Tung problem of distributed lossy compression. Applying the one-shot result for the memoryless broadcast channel in the asymptotic case, we get the entire region of Marton's inner bound without any need for time-sharing. Also, these results are employed in conjunction with multi-dimensional berry-esseen CLT to derive new regions for finite-blocklength regime of Gelfand-Pinsker.

In this paper we develop a finite blocklength version of the Output Statistics of Random Binning (OSRB) framework. This framework is shown to be optimal in the point-to-point case. New second order regions for broadcast channel and wiretap channel with strong secrecy criterion are derived.

In this paper, we study the problem of simulating a DMC channel from another DMC channel. We assume that the input to the channel we are simulating is i.i.d. and that the transmitter and receivers are provided with common randomness at limited rates. We prove bounds for simulating point-to-point, MAC and broadcast channels. As a special case, we recover the achievability part of the result of Cuff for point-to-point channel simulation via a noiseless link and shared randomness.

Cut-set bounds are not, in general, tight for all classes of network communication problems. In this paper, we introduce a new technique for proving converses for the problem of transmission of correlated sources in networks, which results in bounds that are tighter than the corresponding cut-set bounds. We also define the concept of “uncertainty region” which might be of independent interest. We provide a full characterization of this region for the case of two correlated random variables. The bounding technique works as follows: on one hand, we show that if the communication problem is solvable, the uncertainty of certain random variables in the network with respect to imaginary parties that have partial knowledge of the sources must satisfy some constraints that depend on the network architecture. On the other hand, the same uncertainties have to satisfy constraints that only depend on the joint distribution of the sources. Matching these two leads to restrictions on the statistical joint distribution of the sources in communication problems that are solvable over a given network architecture. Our technique also provides nontrivial outer bounds for communication problems with secrecy constraints.

Marton's inner bound is the best known achievable region for a general discrete memoryless broadcast channel. To compute Marton's inner bound one has to solve an optimization problem over a set of joint distributions on the input and auxiliary random variables. The optimizers turn out to be structured in many cases. Finding properties of optimizers not only results in efficient evaluation of the region, but it may also help one to prove factorization of Marton's inner bound (and thus its optimality). The first part of this paper formulates this factorization approach explicitly and states some conjectures and results along this line. The second part of this paper focuses primarily on the structure of the optimizers. This section is inspired by a new binary inequality that recently resulted in a very simple characterization of the sum-rate of Marton's inner bound for binary input broadcast channels. This prompted us to investigate whether this inequality can be extended to larger cardinality input alphabets. We show that several of the results for the binary input case do carry over for higher cardinality alphabets and we present a collection of results that help restrict the search space of probability distributions to evaluate the boundary of Marton's inner bound in the general case. We also prove a new inequality for the binary skew-symmetric broadcast channel that yields a very simple characterization of the entire Marton inner bound for this channel.

In this paper, we study the problem of coordinating two nodes which can only exchange information via a relay at limited rates. The nodes are allowed to do a two-round interactive two-way communication with the relay, after which they should be able to generate i.i.d. copies of two random variables with a given joint distribution within a vanishing total variation distance. We prove inner and outer bounds on the coordination capacity region for this problem. Our inner bound is proved using the technique of “output statistics of random binning" that has recently been developed by Yassaee, et al.

We study the problem of transmission of binary input non-linear functions over a network of mobiles based on CDMA. Motivation for this study comes from the application of using cheap measurement devices installed on personal cellphones to monitor environmental parameters such as air pollution, temperature and noise level. Our model resembles the MAC model of Nazer and Gastpar except that the encoders are restricted to be CDMA encoders. Unlike the work of Nazer and Gastpar whose main attention is transmission of linear functions, we deal with non-linear functions with binary inputs. A main contribution of this paper is a lower bound on the computational capacity for this problem. While in the traditional CDMA system the signature matrix of the CDMA system preferably has independent rows, here the signature matrix of the CDMA system is viewed as the parity check matrix of a linear code, reflecting our treatment of the interference. We also introduce the problem of Slepian-Wolf compression with the same compression matrix.

This paper presents a new and ubiquitous framework for establishing achievability results in network information theory (NIT) problems. The framework is used to prove various new results. To express the main tool, consider a set of discrete memoryless correlated sources (DMCS). Assume that each source (except one, Zn) is randomly binned at a finite rate. We find sufficient conditions on these rates such that the bin indices are nearly mutually independent of each other and of Zn. This is used in conjunction with the Slepian-Wolf (S-W) result to set up the framework. We begin by illustrating this method via examples from channel coding and rate-distortion (or covering problems). Next, we use the framework to prove a new result on the lossy transmission of a source over a broadcast channel. We also prove a new lower bound to a three receiver wiretap broadcast channel under a strong secrecy criterion. We observe that we can directly prove the strong notion of secrecy without resorting to the common techniques, e.g., the leftover hash lemma. We have also used our technique to solve the problem of two-node interactive channel simulation and the problem of coordination via a relay.

In this paper, we study the problem of channel simulation via interactive communication, known as the coordination capacity, in a two-terminal network. We assume that two terminals observe i.i.d. copies of two random variables and would like to generate i.i.d. copies of two other random variables jointly distributed with the observed random variables. The terminals are provided with two-way communication links, and shared common randomness, all at limited rates. Two special cases of this problem are the interactive function computation studied by Ma and Ishwar, and the tradeoff curve between one-way communication and shared randomness studied by Cuff. The latter work had inspired Gohari and Anantharam to study the general problem of channel simulation via interactive communication stated above. However only inner and outer bounds for the special case of no shared randomness were obtained in their work. In this paper we settle this problem by providing an exact computable characterization of the multi-round problem. To show this we employ the technique of “output statistics of random binning” that has been recently developed by the authors.

Cutting a cake is a metaphor for the problem of dividing a resource (cake) among several agents. The problem becomes non-trivial when the agents have different valuations for different parts of the cake (i.e. one agent may like chocolate while the other may like cream). A fair division of the cake is one that takes into account the individual valuations of agents and partitions the cake based on some fairness criterion. Fair division may be accomplished in a distributed or centralized way. Due to its natural and practical appeal, it has been a subject of study in economics under the topic of “Fair Division”. To best of our knowledge the role of partial information in fair division has not been studied so far from an information theoretic perspective. In this paper we study two important algorithms in fair division, namely “divide and choose” and “adjusted winner” for the case of two agents. We quantify the benefit of negotiation in the divide and choose algorithm, and its use in tricking the adjusted winner algorithm. Lastly we consider a centralized algorithm for maximizing the overall welfare of the agents under the Nash collective utility function (CUF). This corresponds to a clustering problem. Drawing a conceptual link between this problem and the portfolio selection problem in stock markets, we prove an upper bound on the increase of the Nash CUF for a clustering refinement.

In this paper the Output Statistics of Random Binning (OSRB) framework is used to prove a new inner bound for the problem of secure channel simulation. Our results subsume some recent results on the secure function computation. We also provide an achievability result for the problem of simultaneously simulating a channel and creating a shared secret key. A special case of this result generalizes the lower bound of Gohari and Anantharam on the source model to include constraints on the rates of the public discussion.

The best known inner bound on the two-receiver general broadcast channel is due to Marton. However this region is not computable (except in certain special cases) as no bounds on the cardinality of its auxiliary random variables exist. Nor is it even clear that the inner bound is a closed set. The main obstacle in proving cardinality bounds is the fact that the traditional use of the Carathéodory theorem, the main known tool for proving cardinality bounds, does not yield a finite cardinality result. One of the main contributions of this paper is the introduction of a new tool based on an identity that relates the second derivative of the Shannon entropy of a discrete random variable (under a certain perturbation) to the corresponding Fisher information. In order to go beyond the traditional Carathéodory type arguments, we identify certain properties that the auxiliary random variables corresponding to the extreme points of the inner bound need to satisfy. These properties are then used to establish cardinality bounds on the auxiliary random variables of the inner bound, thereby proving the computability of the region, and its closedness. Lastly, we establish a conjecture of Nair and Zizhou that Marton's inner bound and the recent outer bound of Nair and El Gamal do not match in general.

We establish a new outer bound for the capacity region of product broadcast channels. This outer bound matches Marton's inner bound for a variety of classes of product broadcast channels whose capacity regions were previously unknown. These classes include product of reversely semi-deterministic and product of reversely more-capable channels. A significant consequence of this new outer bound is that it establishes, via an example, that the previously best known outer-bound is strictly suboptimal for the general broadcast channel. Our example is comprised of a product broadcast channel with two semi-deterministic components in reverse orientation.

Cut-set bounds on achievable rates for network communication protocols are not in general tight. In this paper we introduce a new technique for proving converses for the problem of transmission of correlated sources in networks, that results in bounds that are tighter than the corresponding cut-set bounds. We also define the concept of “uncertainty region” which might be of independent interest. We provide a full characterization of this region for the case of two correlated random variables. The bounding technique works as follows: on one hand we show that if the communication problem is solvable, the uncertainty of certain random variables in the network with respect to imaginary parties that have partial knowledge of the sources must satisfy some constraints that depend on the network architecture. On the other hand, the same uncertainties have to satisfy constraints that only depend on the joint distribution of the sources. Matching these two leads to restrictions on the statistical joint distribution of the sources in communication problems that are solvable over a given network architecture.

In this paper we study the problem of generation of dependent random variables, known as the “coordination capacity” [4], [5], in multiterminal networks. In this model m nodes of the network are observing i.i.d. repetitions of X(1), X(2),..., X(m)distributed according to q(x(1), ..., x(m)). Given a joint distribution q(x(1), ..., x(m), y(1), ..., y(m)), the final goal of the ithnode is to construct the i.i.d. copies of Y(i)after the communication over the network where X(1), X(2),..., X(m), Y(1), Y(2),..., Y(m)are jointly distributed according to q(x(1), ..., x(m), y(1), ..., y(m)). To do this, the nodes can exchange messages over the network at rates not exceeding the capacity constraints of the links. This problem is difficult to solve even for the special case of two nodes. In this paper we prove new inner and outer bounds on the achievable rates for networks with two nodes.

In this paper, we study the Nair-El Gamal outer bound and Marton's inner bound for general two-receiver broadcast channels. We show that the Nair-El Gamal outer bound can be made fully computable. For the inner bound, we show that, unlike in the Gaussian case, for a degraded broadcast channel even without a common message, Marton's coding scheme without a superposition variable is in general insufficient for obtaining the capacity region. Further, we prove various results that help to restrict the search space for computing the sum-rate for Marton's inner bound. We establish the capacity region along certain directions and show that it coincides with Marton's inner bound. Lastly, we discuss an idea that may lead to a larger inner bound.

We study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models, multiple terminals wish to create a shared secret key that is secure from a passive eavesdropper. The terminals have access to a noiseless public communication channel and an additional resource that depends on the model. In the source model, the resource is an external source that repeatedly beams correlated randomness to the terminals; whereas in the channel model, the resource is a secure but noisy discrete memoryless broadcast channel. We derive new lower and upper bounds on the secret key capacity under both the source model and the channel model. The technique used for deriving our bound for the source model is to find certain properties of functions of joint probability distributions which, applied to the joint distribution of the source, will imply that they dominate the secret key capacity, and then prove the bound by a verification argument. A similar technique is used for the channel model. Finally, we also define a problem of communication for omniscience by a neutral observer and establish the equivalence between this new problem and the problem of secret key agreement. This generalizes an earlier result of Csiszár and Narayan.

This is the second part of a two-part paper on information-theoretically secure secret key agreement. This part covers the secret key capacity under the channel model. In this model, multiple terminals wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. The terminals are all connected to a noiseless and authenticated but insecure channel, called the “public channel.” Furthermore, the terminals have access to a secure but noisy discrete memoryless broadcast channel (DMBC). The first terminal can choose a sequence of inputs to the DMBC, which has outputs at the other terminals and at the eavesdropper. After each channel use, the terminals can engage in arbitrarily many rounds of interactive authenticated communication over the public channel. At the end, each legitimate terminal should be able to generate the secret key. In this paper, we derive new lower and upper bounds on the secrecy capacity. In each case, an example is provided to show that the new bound represents a strict improvement over the previously best known bound. This part of the paper is not standalone, and is written under the assumption that the reader has access to Part I, which is published in the same issue.

In this paper, we generalize the well known cutset bound (see for example [1, p. 444]) to the problem of lossy transmission of functions of arbitrarily correlated sources over a discrete memoryless multiterminal network.

The best known inner bound on the two-receiver general broadcast channel without a common message is due to Marton. This result was subsequently generalized in and to broadcast channels with a common message. However the latter region is not computable (except in certain special cases) as no bounds on the cardinality of its auxiliary random variables exist. Nor is it even clear that the inner bound is a closed set. The main obstacle in proving cardinality bounds is the fact that the Carathe¿odory theorem, the main known tool for proving cardinality bounds, does not yield a finite cardinality result. Our new tool is based on an identity that relates the second derivative of the Shannon entropy of a discrete random variable (under a certain perturbation) to the corresponding Fisher information. In order to go beyond the traditional Carathe¿odory type arguments, we identify certain properties that the auxiliary random variables corresponding to the extreme points of the inner bound satisfy. These properties are then used to establish cardinality bounds on the auxiliary random variables of the inner bound, thereby proving the computability of the region, and its closedness. Although existence of cardinality bounds renders Marton's inner bound computable, it is still hard to evaluate the region. It is however shown that the computation can be significantly simplified if we further assume that Marton's inner bound and the recent outer bound of Nair and El Gamal match at the given particular channel. In order to demonstrate this, we consider a large class of binary input broadcast channels and compute maximum of the sum rate of private messages assuming that the inner and the outer bound match at the given broadcast channel. We also show that the inner and the outer bound do not match for some broadcast channels, thus establishing a conjecture of.

We investigate the structure of the polytope underlying the linear programming (LP) decoder introduced by Feldman, Karger, and Wainwright. We first show that for expander codes, every fractional pseudocodeword always has at least a constant fraction of nonintegral bits. We then prove that for expander codes, the active set of any fractional pseudocodeword is smaller by a constant fraction than that of any codeword. We further exploit these geometrical properties to devise an improved decoding algorithm with the same order of complexity as LP decoding that provably performs better. The method is very simple: it first applies ordinary LP decoding, and when it fails, it proceeds by guessing facets of the polytope, and then resolving the linear program on these facets. While the LP decoder succeeds only if the ML codeword has the highest likelihood over all pseudocodewords, we prove that the proposed algorithm, when applied to suitable expander codes, succeeds unless there exists a certain number of pseudocodewords, all adjacent to the ML codeword on the LP decoding polytope, and with higher likelihood than the ML codeword. We then describe an extended algorithm, still with polynomial complexity, that succeeds as long as there are at most polynomially many pseudocodewords above the ML codeword.

We study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models the parties wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. In the channel model, the first party can choose a sequence of inputs to a discrete memoryless channel, which has outputs at the other parties and at the eavesdropper. After each channel use, the parties can engage in arbitrarily many rounds of interactive authenticated communication over a public channel. At the end, each party should be able to generate the key. In the source model, the parties wishing to generate a secret key (as well as the eavesdropper) receive a certain number of independent identically distributed copies of jointly distributed random variables after which the parties are allowed interactive authenticated public communication, at the end of which each party should be able to generate the key. We derive new lower and upper bounds on the secret key rate under the source model and the channel model, and introduce a technique for proving that a given expression bounds the secrecy rate from above in the channel model. Our lower bounds strictly improve what is essentially the best known lower bound in both the source model and the channel model. Our upper bound in the channel model strictly improves the current state of art upper bound. We do not know whether our new upper bound in the source model represents an strict improvement but it includes the current best known bound as a special case.

We derive a new upper bound on the secrecy capacity in the source model with eavesdropper which strictly improves the currently best upper bound, i.e. the double intrinsic information bound of Renner and Wolf. Furthermore, unlike that bound, which is defined only in the case of two terminals, the new upper bound is not specific to the two terminals case. We define a problem of communication for omniscience by a neutral observer and establish the equivalence between this new problem and the problem of secret key agreement.