Improved bounds for multi-sender index coding

Min Li, Lawrence Ong, Sarah J. Johnson

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

11 Citations (Scopus)


We establish new capacity bounds for the multi-sender unicast index-coding problem. We first revisit existing bounds proposed by Sadeghi et al. and identify the suboptimality of their inner bounds in general. We then present a simplified version of the existing multi-sender maximal-acyclic-induced-subgraph outer bound. For the inner bound, we propose joint link-and-sender partitioning to replace sender partitioning in partitioned Distributed Composite Coding (DCC). This leads to a modified DCC (mDCC) that outperforms partitioned DCC and suffices to achieve optimality for some index-coding instances. We also propose cooperative compression of composite messages in composite coding to exploit messages common to different senders to support larger composite rates than those by point-to-point compression in the existing schemes. We then develop a new multi-sender Cooperative Composite Coding (CCC) scheme. CCC further improves upon mDCC in general, and is instrumental to achieve optimality for a number of index-coding instances.

Original languageEnglish
Title of host publication2017 IEEE International Symposium on Information Theory (ISIT)
Subtitle of host publicationproceedings
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages5
ISBN (Electronic)9781509040964
ISBN (Print)9781509040971
Publication statusPublished - 2017
Externally publishedYes
Event2017 IEEE International Symposium on Information Theory, ISIT 2017 - Aachen, Germany
Duration: 25 Jun 201730 Jun 2017

Publication series

ISSN (Electronic)2157-8117


Conference2017 IEEE International Symposium on Information Theory, ISIT 2017


Dive into the research topics of 'Improved bounds for multi-sender index coding'. Together they form a unique fingerprint.

Cite this