Paper ID | D1-S4-T1.3 |
Paper Title |
On the Optimal Transmission Rate for Symmetric Index Coding Problems |
Authors |
Srinivas Reddy Kota, Nujoom Sageer Karat, Nikhil Karamchandani, IIT Bombay, India |
Session |
D1-S4-T1: Index Coding |
Chaired Session: |
Monday, 12 July, 23:00 - 23:20 |
Engagement Session: |
Monday, 12 July, 23:20 - 23:40 |
Abstract |
An Index Coding Problem (ICP) has a central server that possesses files and is connected to multiple users through a shared link. Each user demands a subset of files and possesses another subset of files as side-information. The files which are neither demanded nor possessed as side-information by a user are called its interference files. In a symmetric ICP, the relative positions of side-information and interference files are the same for all the users. In this paper, a general representation for symmetric ICPs is proposed, and using this representation, we give bounds on the optimal transmission rate for a general symmetric ICP. We identify two broad categories of symmetric ICPs: Neighboring Interference ICP (NI-ICP) and Neighboring Side-information ICP (NS-ICP). For a particular class of NI-ICP, we find the optimal transmission rate, and for another class, an order-optimal transmission rate is derived. An upper bound on the optimal transmission rate is established for NS-ICP. Furthermore, for a particular class of NS-ICP, a lower bound for the optimal transmission rate is also derived.
|