We establish that the capacity regions of the discrete memoryless and vector Gaussian multiple access channels with general message sets are achievable with hierarchical successive group decoding, where groups of messages are successively decoded in accordance with the following rule: for each pair of messages known to nested sets of transmitters, the message known to more transmitters is decoded prior to-and not jointly with-the message known to fewer transmitters. This conclusion requires neither rate-splitting nor time-sharing, and is agnostic to whether or not the messages were encoded dependently. For instance, with private messages, hierarchical successive group decoding includes jointly decoding all messages at once, while for degraded messages, it is successive decoding in only one order. A consequence of our main result is that the capacity region of the multiple access channel with general message sets is achievable by time-sharing between only those successive decoding vertices whose decoding order respects the rule described as earlier.

A general inner bound is given for the discrete memoryless broadcast channel with an arbitrary number of users and general message sets, a setting that accounts for the most general form of concurrent groupcasting, with up to exponentially many messages intended for any set of subsets of receivers. Achievability is based on superposition coding and rate-splitting, where each receiver jointly decodes both its desired messages as well as the partial interference assigned to it via rate-splitting. The proof of achievability builds on the techniques for the description and analysis of superposition coding recently developed by the authors for the multiple access channel with general messages.

Two different random coding techniques, both referred to as superposition coding in the literature, have been widely used to obtain inner bounds for the capacity regions of various communication networks. In one, auxiliary codewords are generated independently, and in the other, they are generated in a dependent manner. Using the multiple-access channel with general message sets as a case study, we place the two techniques under a common, order-theoretic framework. The key attribute of this framework is that it explicitly accounts for the acyclic direction and transitivity of the possible auxiliary codeword dependencies, leading to three significant discoveries. First, with respect to a fixed coding distribution, the set of rates achievable by superposition coding with dependent auxiliary codeword generation forms a polymatroid, thereby generalizing the same previously known result for superposition coding with independent auxiliary codewords. Second, we obtain a large class of superposition coding schemes by intermingling dependent and independent auxiliary codeword generation, and demonstrate that the constituent polyhedral achievable rate regions are also polymatroids in each case. The third discovery is that, in the multiple-access channel with general message sets, each associated superposition coding inner bound attains the capacity region. These results demonstrate a tradeoff between the complexity of dependencies in auxiliary codeword generation and that of the function that maps them into transmitted codewords.

The capacity region of the K -user vector Gaussian multiple-access channel with general message sets is established. Furthermore, due to the presence of convexity, both in the discrete and continuous senses, it is shown that this capacity region is efficiently computable. The capacity result is obtained by specializing recent results by the authors for the discrete memoryless multiple-access channel and demonstrating that it suffices to only consider jointly Gaussian input and auxiliary random variables. For this second conclusion, it is shown that jointly Gaussian random variables maximize entropy subject to lattice conditional independence and covariance constraints, a result that is of interest in its own right. Discrete convexity arises since the capacity region is a union of polymatroids. Over each polymatroid, computing the maximal weighted sum rates is simple due to submodularity-a discrete analog of concavity-of the set function associated with the linear inequalities that define the polymatroid. Continuous convexity arises as the set of admissible covariance matrices is convex and the polymatroidal bounds are concave in these covariances.

We present an inner bound for the combination network based on superposition coding and partial interference decoding. This inner bound is tight in the three-user and K-user symmetric cases, where capacity has been previously characterized. However, unlike previous achievability schemes, the scheme presented herein does not require network coding. By avoiding network coding, our inner bound has fewer extraneous parameters. Moreover, it contains the intersection of polymatroids, one for each receiver, a structure that may be more amenable to further analysis than the previous inner bounds for the combination network.

The conditions which govern reliable communication over networks are often given as a union of polyhedra. As increasingly larger networks are considered, these conditions become unwieldy and intractable, unless useful structure can be found in them. An example of a polyhedron with a useful underlying structure is a polymatroid, which despite its exponential number of defining inequalities, has a simple and explicit formula for its vertices. For the multiple access channel with general message sets, we show that each capacity characterization in a large class of capacity characterizations involves polymatroids.

An approximate capacity result is demonstrated for a specific class of interference channels with common information (IC-CI). The class is the semideterministic interference channel of Telatar and Tse, and the outer bound herein generalizes their bound from the case where each transmitter sends only private information to the case where each transmitter sends both private and common information to its corresponding receiver. It is shown that our outer bound is within a quantifiable gap of the inner bound of Jiang-Xin-Garg, a generalization of the Han-Kobayashi region to the IC-CI. Moreover, this result reproduces both the Telatar-Tse result in the case of no common information and a constant-gap-to-capacity result for the Gaussian IC-CI.