Index coding and local partial clique covers

Abhishek Agarwal, Arya Mazumdar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Index coding, or broadcasting with side information, is a network coding problem of most fundamental importance. In this problem, given a directed graph, each vertex represents a user with a need of information, and the neighborhood of each vertex represents the side information availability to that user. The aim is to find an encoding to minimum number of bits (optimal rate) that, when broadcasted, will be sufficient to the need of every user. Not only the optimal rate is intractable, but it is also very hard to characterize with some other well-studied graph parameter or with a simpler formulation, such as a linear program. Recently there have been a series of works that address this question and provide explicit schemes for index coding as the optimal value of a linear program with rate given by well-studied properties such as local chromatic number or partial clique-covering number. There has been a recent attempt to combine these existing notions of local chromatic number and partial clique covering into a unified notion denoted as the local partial clique cover (Arbabjolfaei and Kim, 2014). We present a generalized novel upper-bound (encoding scheme) - in the form of the minimum value of a linear program - for optimal index coding. Our bound also combines the notions of local chromatic number and partial clique covering into a new definition of the local partial clique cover, which outperforms both the previous bounds, as well as beats the previous attempt to combination.

Original languageEnglish (US)
Title of host publication2016 International Conference on Signal Processing and Communications, SPCOM 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509017461
DOIs
StatePublished - Nov 16 2016
Event11th International Conference on Signal Processing and Communications, SPCOM 2016 - Bangalore, India
Duration: Jun 12 2016Jun 15 2016

Publication series

Name2016 International Conference on Signal Processing and Communications, SPCOM 2016

Other

Other11th International Conference on Signal Processing and Communications, SPCOM 2016
Country/TerritoryIndia
CityBangalore
Period6/12/166/15/16

Bibliographical note

Funding Information:
Research supported by NSF grants CCF 1318093 and CAREER CCF 1453121.

Publisher Copyright:
© 2016 IEEE.

Fingerprint

Dive into the research topics of 'Index coding and local partial clique covers'. Together they form a unique fingerprint.

Cite this