Improved Converses and Gap Results for Coded Caching

Chien Yi Wang; Shirin Saeedi Bidokhti; Michèle Wigger

doi:10.1109/TIT.2018.2856885

Improved Converses and Gap Results for Coded Caching

Chien Yi Wang, Shirin Saeedi Bidokhti, Michèle Wigger

Research output: Contribution to journal › Article › peer-review

Abstract

Improved lower bounds are derived on the average and worst case rate-memory tradeoffs of the Maddah-Ali and Niesen-coded caching scenario. For any number of users and files and for arbitrary cache sizes, the multiplicative gap between the exact rate-memory tradeoff and the new lower bound is shown to be less than 2.315 in the worst case scenario and 2.507 in the average-case scenario.

Original language	English
Article number	8412584
Pages (from-to)	7051-7062
Number of pages	12
Journal	IEEE Transactions on Information Theory
Volume	64
Issue number	11
DOIs	https://doi.org/10.1109/TIT.2018.2856885
Publication status	Published - 1 Nov 2018
Externally published	Yes

Keywords

Caching
index coding
rate-memory tradeoff
source coding

Access to Document

10.1109/TIT.2018.2856885

Cite this

@article{ef1066a787b04a1f8a814189e96ec9dd,

title = "Improved Converses and Gap Results for Coded Caching",

abstract = "Improved lower bounds are derived on the average and worst case rate-memory tradeoffs of the Maddah-Ali and Niesen-coded caching scenario. For any number of users and files and for arbitrary cache sizes, the multiplicative gap between the exact rate-memory tradeoff and the new lower bound is shown to be less than 2.315 in the worst case scenario and 2.507 in the average-case scenario.",

keywords = "Caching, index coding, rate-memory tradeoff, source coding",

author = "Wang, \{Chien Yi\} and Bidokhti, \{Shirin Saeedi\} and Mich{\`e}le Wigger",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.",

year = "2018",

month = nov,

day = "1",

doi = "10.1109/TIT.2018.2856885",

language = "English",

volume = "64",

pages = "7051--7062",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

number = "11",

}

TY - JOUR

T1 - Improved Converses and Gap Results for Coded Caching

AU - Wang, Chien Yi

AU - Bidokhti, Shirin Saeedi

AU - Wigger, Michèle

PY - 2018/11/1

Y1 - 2018/11/1

N2 - Improved lower bounds are derived on the average and worst case rate-memory tradeoffs of the Maddah-Ali and Niesen-coded caching scenario. For any number of users and files and for arbitrary cache sizes, the multiplicative gap between the exact rate-memory tradeoff and the new lower bound is shown to be less than 2.315 in the worst case scenario and 2.507 in the average-case scenario.

AB - Improved lower bounds are derived on the average and worst case rate-memory tradeoffs of the Maddah-Ali and Niesen-coded caching scenario. For any number of users and files and for arbitrary cache sizes, the multiplicative gap between the exact rate-memory tradeoff and the new lower bound is shown to be less than 2.315 in the worst case scenario and 2.507 in the average-case scenario.

KW - Caching

KW - index coding

KW - rate-memory tradeoff

KW - source coding

U2 - 10.1109/TIT.2018.2856885

DO - 10.1109/TIT.2018.2856885

M3 - Article

AN - SCOPUS:85050239822

SN - 0018-9448

VL - 64

SP - 7051

EP - 7062

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 11

M1 - 8412584

ER -

Improved Converses and Gap Results for Coded Caching

Abstract

Keywords

Access to Document

Fingerprint

Cite this