On the Capacity Region for Index Coding

Abstract

A new inner bound on the capacity region of a general index coding problem is established. Unlike most existing bounds that are based on graph theoretic or algebraic tools, the bound is built on a random coding scheme and optimal decoding, and has a simple polymatroidal single-letter expression. The utility of the inner bound is demonstrated by examples that include the capacity region for all index coding problems with up to five messages (there are 9846 nonisomorphic ones).

5 pages, 6 figures, accepted to the 2013 IEEE International Symposium on Information Theory (ISIT), Istanbul, Turkey, July 2013

References in corpus (5)

• Broadcasting with side information
• Index coding via linear programming
• An Equivalence between Network Coding and Index Coding
• Local Graph Coloring and Index Coding
• Index Coding Capacity: How far can one go with only Shannon Inequalities?

Cited by in corpus (43)

• The Single-Uniprior Index-Coding Problem: The Single-Sender Case and The Multi-Sender Extension
• Rate-Memory Trade-off for Multi-access Coded Caching with Uncoded Placement
• Order-Optimal Rate of Caching and Coded Multicasting with Random Demands
• Interlinked Cycles for Index Coding: Generalizing Cycles and Cliques
• Structured Index Coding Problem and Multi-access Coded Caching
• Secure Index Coding: Existence and Construction
• Graph-Theoretic Approaches to Two-Sender Index Coding
• Information Theoretic Caching: The Multi-User Case
• Optimal Finite-Length and Asymptotic Index Codes for Five or Fewer Receivers
• Linear Codes are Optimal for Index-Coding Instances with Five or Fewer Receivers
• Cooperative Multi-Sender Index Coding
• Index Coding Capacity: How far can one go with only Shannon Inequalities?
• On the Optimality of Uncoded Cache Placement
• Structural Characteristics of Two-Sender Index Coding
• Secure Index Coding with Security Constraints on Receivers
• Generalized Interlinked Cycle Cover for Index Coding
• Structural Properties of Index Coding Capacity Using Fractional Graph Theory
• Perfectly Secure Index Coding
• Unselfish Coded Caching can Yield Unbounded Gains over Symmetrically Selfish Caching
• A New Combinatorial Coded Design for Heterogeneous Distributed Computing
• Linear Index Coding With Multiple Senders and Extension to a Cellular Network
• Topological Interference Management with Transmitter Cooperation
• A New Index Coding Scheme Exploiting Interlinked Cycles
• Distributed Index Coding
• Capacity Theorems for Distributed Index Coding
• Equivalences Between Network Codes With Link Errors and Index Codes With Side Information Errors
• A Rate-Distortion Approach to Index Coding
• On Critical Index Coding Problems
• Three Stories on a Two-sided Coin: Index Coding, Locally Recoverable Distributed Storage, and Guessing Games on Graphs
• Alignment based Network Coding for Two-Unicast-Z Networks
• Index Coding and Network Coding via Rank Minimization
• The Optimality of Partial Clique Covering for Index Coding
• Approximate Capacity of Index Coding for Some Classes of Graphs
• Transmission and Scheduling Aspects of Distributed Storage and Their Connections with Index Coding
• A class of index coding problems with rate 1/3
• Privacy-Utility Tradeoff in a Guessing Framework Inspired by Index Coding
• On D2D Caching with Uncoded Cache Placement
• Generalized Alignment Chain: Improved Converse Results for Index Coding
• The DoF Region of the Three-Receiver MIMO Broadcast Channel with Side Information and Its Relation to Index Coding Capacity
• On the Capacity for Distributed Index Coding
• Approximate Capacity of a Class of Partially Connected Interference Channels
• An Optimal Linear Coding for Index Coding Problem
• Optimality of Orthogonal Access for One-dimensional Convex Cellular Networks