A Polynomial-Time Algorithm for Pliable Index Coding

Linqi Song; Christina Fragouli

doi:10.1109/ISIT.2016.7541273

A Polynomial-Time Algorithm for Pliable Index Coding

Linqi Song, Christina Fragouli

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

4 Citations (Scopus)

Abstract

Pliable index coding considers a server with m messages and n clients where each client has as side information a subset of the messages. We seek to minimize the number of transmissions the server should make, so that each client receives (any) one message she does not already have. Previous work has shown that the server can achieve this using at most O(log²(n)) transmissions and needs at least Ω(log(n)) transmissions in the worst case, but finding a code of optimal length is NP-hard. In this paper, we design a polynomial-time algorithm that uses less than O(log²(n)) transmissions, i.e., almost worst-case optimal. We also establish a connection between the pliable index coding problem and the minrank problem over a family of mixed matrices.

Original language	English
Title of host publication	Proceedings 2016 IEEE International Symposium on Information Theory (ISIT 2016)
Publisher	IEEE
Pages	120-124
ISBN (Electronic)	9781509018062
ISBN (Print)	9781509018079
DOIs	https://doi.org/10.1109/ISIT.2016.7541273
Publication status	Published - Jul 2016
Externally published	Yes
Event	2016 IEEE International Symposium on Information Theory (ISIT 2016) - Barcelona, Spain Duration: 10 Jul 2016 → 15 Jul 2016

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
ISSN (Print)	2157-8095
ISSN (Electronic)	2157-8117

Conference

Conference	2016 IEEE International Symposium on Information Theory (ISIT 2016)
Abbreviated title	ISIT 2016
Country/Territory	Spain
City	Barcelona
Period	10/07/16 → 15/07/16

Access Output

10.1109/ISIT.2016.7541273

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{5390170355fd43cebf92373508366a90,

title = "A Polynomial-Time Algorithm for Pliable Index Coding",

abstract = "Pliable index coding considers a server with m messages and n clients where each client has as side information a subset of the messages. We seek to minimize the number of transmissions the server should make, so that each client receives (any) one message she does not already have. Previous work has shown that the server can achieve this using at most O(log2(n)) transmissions and needs at least Ω(log(n)) transmissions in the worst case, but finding a code of optimal length is NP-hard. In this paper, we design a polynomial-time algorithm that uses less than O(log2(n)) transmissions, i.e., almost worst-case optimal. We also establish a connection between the pliable index coding problem and the minrank problem over a family of mixed matrices.",

author = "Linqi Song and Christina Fragouli",

year = "2016",

month = jul,

doi = "10.1109/ISIT.2016.7541273",

language = "English",

isbn = "9781509018079",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "IEEE",

pages = "120--124",

booktitle = "Proceedings 2016 IEEE International Symposium on Information Theory (ISIT 2016)",

address = "United States",

note = "2016 IEEE International Symposium on Information Theory (ISIT 2016), ISIT 2016 ; Conference date: 10-07-2016 Through 15-07-2016",

}

Song, L & Fragouli, C 2016, A Polynomial-Time Algorithm for Pliable Index Coding. in Proceedings 2016 IEEE International Symposium on Information Theory (ISIT 2016)., 7541273, IEEE International Symposium on Information Theory - Proceedings, IEEE, pp. 120-124, 2016 IEEE International Symposium on Information Theory (ISIT 2016), Barcelona, Spain, 10/07/16. https://doi.org/10.1109/ISIT.2016.7541273

A Polynomial-Time Algorithm for Pliable Index Coding. / Song, Linqi; Fragouli, Christina.
Proceedings 2016 IEEE International Symposium on Information Theory (ISIT 2016). IEEE, 2016. p. 120-124 7541273 (IEEE International Symposium on Information Theory - Proceedings).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - A Polynomial-Time Algorithm for Pliable Index Coding

AU - Song, Linqi

AU - Fragouli, Christina

PY - 2016/7

Y1 - 2016/7

N2 - Pliable index coding considers a server with m messages and n clients where each client has as side information a subset of the messages. We seek to minimize the number of transmissions the server should make, so that each client receives (any) one message she does not already have. Previous work has shown that the server can achieve this using at most O(log2(n)) transmissions and needs at least Ω(log(n)) transmissions in the worst case, but finding a code of optimal length is NP-hard. In this paper, we design a polynomial-time algorithm that uses less than O(log2(n)) transmissions, i.e., almost worst-case optimal. We also establish a connection between the pliable index coding problem and the minrank problem over a family of mixed matrices.

AB - Pliable index coding considers a server with m messages and n clients where each client has as side information a subset of the messages. We seek to minimize the number of transmissions the server should make, so that each client receives (any) one message she does not already have. Previous work has shown that the server can achieve this using at most O(log2(n)) transmissions and needs at least Ω(log(n)) transmissions in the worst case, but finding a code of optimal length is NP-hard. In this paper, we design a polynomial-time algorithm that uses less than O(log2(n)) transmissions, i.e., almost worst-case optimal. We also establish a connection between the pliable index coding problem and the minrank problem over a family of mixed matrices.

UR - http://www.scopus.com/inward/record.url?scp=84985998199&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84985998199&origin=recordpage

U2 - 10.1109/ISIT.2016.7541273

DO - 10.1109/ISIT.2016.7541273

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9781509018079

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 120

EP - 124

BT - Proceedings 2016 IEEE International Symposium on Information Theory (ISIT 2016)

PB - IEEE

T2 - 2016 IEEE International Symposium on Information Theory (ISIT 2016)

Y2 - 10 July 2016 through 15 July 2016

ER -

A Polynomial-Time Algorithm for Pliable Index Coding

Abstract

Publication series

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this