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

We establish a recent conjecture regarding the Gaussian signaling region for the Z-interference channel. This helps us isolate a large class of parameters for which multiplexing, or noisebergs, are not needed for the computation of the optimal Gaussian signaling region.

Ruzsa’s equivalence theorem provided a framework for converting certain families of inequalities in additive combinatorics to entropic inequalities (which sometimes did not possess stand-alone entropic proofs). In this work, we first establish formal equivalences between some families (different from Ruzsa) of inequalities in additive combinatorics and entropic ones. As a first step to further these equivalences, we establish an information-theoretic characterization of the magnification ratio that could also be of independent interest.

In this paper, we present a family of conjectures on the optimality of the dictator function among all Boolean functions for a new family of$\Phi$-entropies. Our main theorem shows that there is an ordering of these conjectures, in that if the conjecture is established for a value$\alpha$, then it holds for any$\beta$:$\beta\geq \alpha$• For the parameter range$\frac{1}{2}\leq\alpha, \beta < 1$, this family of conjectures is stronger than the mutual information conjecture, originally proposed in a paper by Courtade and Kumar. By considering a limiting value of the noise parameter$\rho$, we show how these conjectures relate to isoperimetric inequalities on the Boolean Hypercube of a flavor first considered by Talagrand and later by Kahn and Park. Finally, we obtain bounds to our conjecture using ideas from the proofs of isoperimetric inequalities.1

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

The doubling-followed-by-rotation trick to prove the extremality of Gaussian distributions has been a valuable tool in information theory. In particular, the above trick has been used to establish the Gaussian extremality of a family of inequalities that unifies the Entropy Power Inequality and the Brascamp-Lieb inequalities. Here, we develop a technique (similar to the one in the continuous case) to prove the extremality of Haar distributions for a similar family of inequalities in finite Abelian groups.

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.

Ruzsa’s equivalence theorem provided a framework for converting certain families of inequalities in additive combinatorics to entropic inequalities (which sometimes did not possess stand-alone entropic proofs). In this work, we first establish formal equivalences between some families (different from Ruzsa) of inequalities in additive combinatorics and entropic ones. Secondly, we provide stand-alone entropic proofs for some previously known entropic inequalities that we established via Ruzsa’s equivalence theorem. As a first step to further these equivalences, we provide an information theoretic characterization of the magnification ratio that is also of independent interest.

In this paper we derive an inequality relating linear combinations of mutual information between subsets of mutually independent random variables and an auxiliary random variable. One choice of a family of auxiliary variables leads to a new proof of a Stam-type inequality regarding the Fisher Information of sums of independent random variables. Another choice of a family of auxiliary random variables leads to new results as well as new proofs of results relating to strong data processing constants and maximal correlation between sums of independent random variables. Other results obtained include convexity of Kullback–Leibler divergence over a parameterized path along pairs of binomial and Poisson distributions, as well as a new duality-based argument relating the Stam-type inequality and entropy power inequality.

In this paper we derive an inequality relating linear combinations of mutual information between subsets of mutually independent random variables and an auxiliary random variable. As corollaries of this inequality, we obtain new results and generalizations and new proofs of known results.

Certain families of non-convex optimization problems involving linear combinations of log-determinants of positive definite matrices are shown to have a unique local maximizer. These geometric results are established using information-theoretic arguments. We demonstrate these results for three different families: two of which arise in the study of the capacity region of the vector Gaussian broadcast channel and another one in the study of computing the optimal generalized Brascamp-Lieb constant.

The entropy power inequality (EPI) and the Brascamp-Lieb inequality (BLI) are fundamental inequalities concerning the differential entropies of linear transformations of random vectors. The EPI provides lower bounds for the differential entropy of linear transformations of random vectors with independent components. The BLI, on the other hand, provides upper bounds on the differential entropy of a random vector in terms of the differential entropies of some of its linear transformations. In this paper, we define a family of entropy functionals, which we show are subadditive. We then establish that Gaussians are extremal for these functionals by adapting a proof technique from Geng and Nair (2014). As a consequence, we obtain a new entropy inequality that generalizes both the BLI and EPI. By considering a variety of independence relations among the components of the random vectors appearing in these functionals, we also obtain families of inequalities that lie between the EPI and the BLI.

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 generalize a convexity result due to Wyner and Ziv to channels with binary inputs and arbitrary outputs. This results in a convex reformulation of some non-convex optimization problems that arise naturally in multi-user information theory.

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.

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

In this paper we establish that a maximizer of a non-convex problem in positive semidefinite matrices has a certain property using information-theoretic methods. Further, we propose a Gaussian extremality conjecture, which if true, would imply that Gaussian signaling achieves the capacity region of the Gaussian Z-interference channel. The non-convex problem mentioned above arose naturally in the reduction from the conjecture to the optimality of Gaussian signaling.

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.

In a seminal work Körner and Marton showed that for computing the module-two sum of doubly symmetric binary sources, linear codes achieved the optimal rates and outperformed random coding and binning based arguments. Körner also showed the optimality of Slepian-Wolf based random coding for the same problem for a different class of pairwise distributions. We show that the optimal sum-rate is given by linear codes for a larger class of binary distributions, thus extending the optimality results for this problem.

This paper is mostly a follow up on the work of Etkin and Ordentlich that studied the capacity regions of binary input deterministic interference channels. The only binary input deterministic interference channel whose capacity region is unknown (up to isomorphism) is when one receiver receives the Boolean AND of the two transmitted symbols, and the other receiver obtains the Boolean OR of the two transmitted symbols. Etkin and Ordentlich stated in the paper that they believed that time-division would be the capacity region for this interference channel. In this paper we show that one can achieve rates outside the time-division region. That time-division yields the zero-error capacity region for this setting is known as Simonyi's sand-glass conjecture, a statement that has received considerable attention in the combinatorics community. Various upper-bounds on the sum-rate of the zero-error capacity region had been proposed in the combinatorics community. In this paper we evaluate an outer bound to the (traditional notion of) capacity region due to Etkin and Ordentlich and show that this yields, surprisingly, a tighter bound that the best known bound for the sand-glass problem. Finally, we establish the capacity region of the some special classes of binary input interference channels by improving on the outer-bound proposed by Etkin and Ordentlich.

The entropy power inequality (EPI) and the Brascamp-Lieb inequality (BLI) are fundamental inequalities concerning the differential entropies of linear transformations of random vectors. The EPI provides lower bounds for the differential entropy of linear transformations of random vectors with independent components. The BLI, on the other hand, provides upper bounds on the differential entropy of a random vector in terms of the differential entropies of some of its linear transformations. In this paper, we define a family of entropy functionals, which we show are subadditive. We then establish that Gaussians are extremal for these functionals by mimicking the idea in Geng and Nair (2014). As a consequence, we obtain a new entropy inequality that generalizes both the BLI and EPI. By considering a variety of independence relations among the components of the random vectors appearing in these functionals, we also obtain families of inequalities that lie between the EPI and the BLI.

A structured code that improves the previously best known exponential asymptotic lower bound for the maximum cardinality of a pairwise-colliding set of permutations is presented. The main contribution is an explicit construction of an infinite recursion of pairwise-colliding sets of partial-permutations.

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.

We establish that the multi-letter extension of the Han-Kobayashi achievable region with temporally correlated vector Gaussian inputs matches the Han-Kobayashi achievable region with scalar Gaussian inputs for the Gaussian interference channel.

In this paper, we obtain the reverse hypercontractive region for the pair of variables (X, Y) where X is a uniformly distributed binary random variable and Y (a ternary random variable) is obtained by passing X through a symmetric binary erasure channel (BEC), for a non-trivial range of parameters. The technique used builds on two recent results: a) characterization of reverse hypercontractivity using information measures, and b) computation of the forward hypercontractive region for the BEC.

In this article, we resolve open problem 8.2 in [1]. We show that superposition coding is sub-optimal for a three receiver broadcast channel with two message sets (M0, M1) where two of the three receivers need to decode messages M0, M1) while the remaining one just needs to decode the message M0.

We study the optimality of Gaussian signaling (with power control) for the two-user scalar Gaussian interference channel. The capacity region is shown to exhibit a discontinuity of slope around the sum-rate point for a subset of the very weak interference channel. We also show that using colored Gaussians (multi-letter) does not improve on the single-letter region of Gaussian signaling with power control. Finally, we also present an approach to test the optimality of Gaussian signaling motivated by some calculations of the slope of Han-Kobayashi region near the corner point of the Z-interference channel.

We derive an equivalent characterization, using information measures, for a class of reverse Brascamp-Lieb type inequalities. These inequalities contain, in particular, the family of reverse hypercontractive inequalities.

We use an equivalent characterization of hypercontractive parameters using relative entropy to compute the hypercontractive region for the binary erasure channel. A similar analysis also recovers the celebrated result for the binary symmetric channel, also called the Bonami-Beckner inequality.

This paper shows that the slope at each corner point of the capacity region of the general broadcast channel coincides with that of the randomized time division (hence the Marton) inner bound and the Nair-El Gamal (as well as the Körner-Marton) outer bound. We then show that the optimal superposition coding inner bound by Bandemer, El Gamal, and Kim can be simplified to the convex closure of the union of the Cover-Bergmans UX region and the Cover-van der Meulen UV region. Generalizing a result by Hajek and Pursely on the skewed binary symmetric broadcast channel, we show that for binary input broadcast channels, the UV region reduces to time division further simplifying the superposition coding inner bound. Finally we establish necessary and sufficient conditions for the optimality of the superposition inner bound for skewed binary broadcast channels.

We obtain the strong data processing constant for sums of real-valued i.i.d. random variables by means of a very simple information-theoretic proof. As a corollary, we recover a classical result concerning the maximal correlation between sums of a sequence of real-valued i.i.d. random variables.

Han-Kobayashi achievable region forms the best known inner bound for a general discrete memoryless interference channel. We show that the capacity region can be strictly larger than the Han-Kobayashi region for some channel realizations, and hence the strict sub-optimality of Han-Kobayashi achievable region.

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.

We derive a genie-based outer bound for the sum rate of discrete memoryless interference channels. We define a class of very weak interference channels and study a sub-class called the binary skewed-Z interference channel. We use the genie-based outer bound to deduce the sum-capacity in a nontrivial regime of parameters for this sub-class.

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.

A novel method for establishing the optimality of Gaussian auxiliary random variables in multiterminal information theory problems is developed. This method is then employed to show that Marton's inner bound achieves the capacity region of the two-receiver Gaussian vector broadcast channel with private and common messages.

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.

We establish an information inequality concerning five random variables. This inequality is motivated by the sum-rate evaluation of Marton's inner bound for two receiver broadcast channels with a binary input alphabet. We establish that randomized time-division strategy achieves the sum rate of Marton's inner bound for all binary input broadcast channels. We also obtain an improved cardinality bound for evaluating the maximum sum rate given by Marton's inner bound for all broadcast channels. Using these tools we explicitly evaluate the inner and outer bounds for the binary skew-symmetric broadcast channel and demonstrate a gap between the bounds.

We establish capacity regions for some classes of broadcast channels with binary inputs and symmetric outputs. We investigate the more capable partial order and establish that the binary erasure channel and the binary symmetric channel form the two extremes for channels having the same capacity. Further, we apply the results to identify a class of broadcast channels for which the best-known inner and outer bounds on the capacity region differ.

We develop a new method for showing the optimality of the Gaussian distribution in multiterminal information theory problems. As an application of this method we show that Marton's inner bound achieves the capacity of the vector Gaussian broadcast channels with common message.

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 show that superposition coding is not optimal for three-receiver more capable channels. The optimality of superposition coding region has been open for k-receiver (k ≥ 3) more capable broadcast channel. The main contribution is in identifying a counterexample to demonstrate that superposition coding is sub-optimal. We also compute the capacity region for the counter example. On the other hand, we show that the sum-capacity for a k-receiver more capable broadcast channel is obtained by transmitting all the information to the most capable receiver.

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.

We determine the capacity region of a 3-receiver less noisy broadcast channel. The difficulty in extending the two-receiver result to three-receivers involves extending the Csiszar-sum lemma to three or more sequences, a standard difficulty in this area. In this work we bypass the difficulty by using a new information inequality, for less noisy receivers, that is employed in the converse. We also generalize our result to obtain the capacity region for a class of less noisy receivers.

We study the capacity regions of broadcast channels with binary inputs and symmetric outputs. We study the partial order induced by the more capable ordering of broadcast channels for channels belonging to this class. In particular this leads to some surprising connections regarding various notions of dominance of receivers. This study also helps us isolate some classes of symmetric channels where the best known inner and outer bounds differ.

We establish an information inequality that is intimately connected to the evaluation of the sum rate given by Marton's inner bound for two-receiver broadcast channels with a binary input alphabet. This generalizes a recent result where the inequality was established for a particular channel, the binary skew-symmetric broadcast channel. The inequality implies that randomized time-division strategy indeed achieves the sum rate of Marton's inner bound for all binary input broadcast channels.

Determining the capacity region of a broadcast channel consisting of k-receivers that lie in a less noisy sequence has been open, when k ≥ 3. We solve this problem for the case k = 3. Generalizing this result, we prove that superposition coding is optimal for a class of broadcast channels with a sequence of less noisy receivers. The main contribution of this work is a new information inequality, for less noisy receivers, used in the converse.

Motivated by a simple broadcast channel, we generalize the notions of aless noisyreceiver and amore capablereceiver to anessentially less noisy receiverand anessentially more capablereceiver, respectively. We establish the capacity regions of these classes by borrowing on existing techniques; however, these new classes contain additional interesting classes of broadcast channels, including the BSC/BEC broadcast channel. We also establish the relationships between the new classes and the existing classes.

The Marton-Gelfand-Pinsker inner bound on the capacity region of broadcast channels was extended by Han-Costa to include arbitrarily correlated sources where the capacity region is replaced by an admissible source region. The main arguments of Han-Costa are correct but unfortunately the authors overlooked an inequality in their derivation. The corrected region is presented and the absence of the omitted inequality is shown to sometimes admit sources that are not admissible.

Motivated by a simple broadcast channel, we generalize the notions of a less noisy receiver and a more capable receiver to an essentially less noisy receiver and an essentially more capable receiver respectively. We establish the capacity regions of these classes by borrowing on existing techniques to obtain the characterization of the capacity region for certain new and interesting classes of broadcast channels. We also establish the relationships between the new classes and the existing classes.

We consider a broadcast channel with 3 receivers and 2 messages (M0, M1) where two of the three receivers need to decode messages (M0, M1) while the remaining one just needs to decode the message M0. We study the best known inner and outer bounds under this setting, in an attempt to find the deficiencies with the current techniques of establishing the bounds. We produce a simple example where we are able to explicitly evaluate the inner bound and show that it differs from the general outer bound. For a class of channels where the general inner and outer bounds differ, we use a new argument to show that the inner bound is tight.

Korner and Marton established the capacity region for the two-receiver broadcast channel with degraded message sets. Recent results and conjectures suggest that a straightforward extension of the Korner-Marton region to more than two receivers is optimal. This paper shows that this is not the case. We establish the capacity region for a class of three-receiver broadcast channels with two-degraded message sets and show that it can be strictly larger than the straightforward extension of the Korner-Marton region. The idea is to split the private message into two parts, superimpose one part onto the ldquocloud centerrdquo representing the common message, and superimpose the second part onto the resulting ldquosatellite codeword.rdquo One of the receivers finds the common message directly by decoding the ldquocloud center,rdquo a second receiver finds itindirectlyby decoding a satellite codeword, and a third receiver finds it by jointly decoding the transmitted codeword. This idea is then used to establish new inner and outer bounds on the capacity region of the general three-receiver broadcast channel with two and three degraded message sets. We show that these bounds are tight for some nontrivial cases. The results suggest that finding the capacity region of the three-receiver broadcast channel with degraded message sets is at least as hard finding as the capacity region of the general two-receiver broadcast channel with common and private message.

Körner and Marton established the capacity region for the 2-receiver broadcast channel with degraded message sets. Recent results and conjectures suggest that a straightforward extension of the Körner-Marton region to more than 2 receivers is optimal. This paper shows that this is not the case. We establish the capacity region for a class of 3-receiver broadcast channels with 2 degraded message sets and show that it can be strictly larger than the straightforward extension of the Körner-Marton region. The key new idea is indirect decoding, whereby a receiver who cannot directly decode a cloud center, finds it indirectly by decoding satellite codewords. This idea is then used to establish new inner bounds on the capacity region of the general 3-receiver broadcast channel with 2 and 3 degraded message sets. These bounds are tight for some nontrivial cases.

We consider the multi-source network coding problem in cyclic networks. This problem involves several difficulties not found in acyclic networks, due to additional causality requirements. This paper highlights the difficulty of these causality conditions by analyzing two example cyclic networks which are structurally similar. Both networks have an essentially identical network code which appears to transmit all information from the sources to the sinks; however, this network code is invalid since it violates causality. We show that, in one of the networks, the invalid code can be modified to obey causality, whereas in the other network this is impossible. This unachievability result is proven by a new information inequality for causal coding schemes in a simple cyclic network.

We construct a deterministic fully polynomial time approximationscheme (FPTAS) for computing the total number of matchings in abounded degree graph. Additionally, for an arbitrary graph, weconstruct a deterministic algorithm for computing approximately thenumber of matchings within running time exp(O(√n log2n)),where n is the number of vertices.

An outer bound to the capacity region of the two-receiver discrete memoryless broadcast channel is given. The outer bound is tight for all cases where the capacity region is known. When specialized to the case of no common information, this outer bound is contained in the Koumlrner-Marton outer bound. This containment is shown to be strict for the binary skew-symmetric broadcast channel. Thus, this outer bound is in general tighter than all other known outer bounds.

An outer bound to the capacity region of the two-receiver discrete memoryless broadcast channel is given. The outer bound is tight for all cases where the capacity region is known. When specialized to the case of no common information, this outer bound is shown to be contained in the Korner-Marton outer bound. This containment is shown to be strict for the binary skew-symmetric broadcast channel. Thus, this outer bound is in general tighter than all other known outer bounds on the discrete memoryless broadcast channel

Recent work by Ordentlich and Weissman put forth a new approach for bounding the entropy rate of a hidden Markov process via the construction of a related Markov process. We use this approach to study the behavior of the filtering error probability and the entropy rate of a hidden Markov process in the rare transitions regime. In this paper, we restrict our attention to the case of a two state Markov chain that is corrupted by a binary symmetric channel. Using this approach we recover the results on the optimal filtering error probability of Khasminskii and Zeitouni. In addition, this approach sheds light on the terms that appear in the expression for the optimal filtering error probability. We then use this approach to obtain tight estimates of the entropy rate of the process in the rare transitions regime. This leads to tight estimates on the capacity of the Gilbert-Elliot channel in the rare transitions regime

Consider the problem of minimizing cost when assigning n jobs to n machines. An assignment is a one-to-one mapping of jobs onto the machines. Assume that the cost of executing job i on machine j is C/sub ij/, i,j = 1,...,n. When the c/sub ij/ are i.i.d. exponentials of mean 1, Parisi conjectured that the average cost of the minimum assignment equals /spl Sigma//sub i=1//sup n/1/i/sup 2/. Recently, the authors, and independently, Linusson and Wastlund, have proved this conjecture. In the above work the authors also made a refined conjecture that, if established, would yield another proof of the Parisi's conjecture. This paper establishes the refined conjecture, thus providing a new proof of Parisi's conjecture.

Suppose that there are n jobs and n machines and it costs c/sub ij/ to execute job i on machine j. The assignment problem concerns the determination of a one-to-one assignment of jobs onto machines so as to minimize the cost of executing all the jobs. The average case analysis of the classical random assignment problem has received a lot of interest in the recent literature, mainly due to the following pleasing conjecture of Parisi: The average value of the minimum-cost permutation in an n /spl times/ n matrix with i.i.d. exp(1) entries equals /spl Sigma//sub i=1//sup n/ 1/(i/sup 2/). D. Coppersmith and G. Sorkin (1999) have generalized Parisi's conjecture to the average value of the smallest k-assignment when there are n jobs and m machines. We prove both conjectures based on a common set of combinatorial and probabilistic arguments.

The paper develops algorithms for minimizing the energy required to transmit packets in a wireless environment. It is motivated by the following observation: In many channel coding schemes it is possible to significantly lower the transmission energy by transmitting packets over a long period of time. Based on this observation, we show that for a variety of scenarios the offline energy-efficient transmission scheduling problem reduces to a convex optimization problem. Unlike for the special case of a single transmitter-receiver pair studied by (see Prabhakar, Uysal-Biyikoglu and El Gamal. Proc. IEEE Infocom 2001), the problem does not, in general, admit a closed-form solution when there are multiple users. By exploiting the special structure of the problem, however, we are able to devise energy-efficient transmission schedules. For the downlink channel, with a single transmitter and multiple receivers, we devise an iterative algorithm, called MoveRight, that yields the optimal offline schedule. The MoveRight algorithm also optimally solves the downlink problem with additional constraints imposed by packet deadlines and finite transmit buffers. For the uplink (or multiaccess) problem MoveRight optimally determines the offline time-sharing schedule. A very efficient online algorithm, called MoveRightExpress, that uses a surprisingly small look-ahead buffer is proposed and is shown to perform competitively with the optimal offline schedule in terms of energy efficiency and delay.