2017/01/24 by Shanmugam, Karthikeyan, Antonia M. Tulino, Alexandros G. Dimakis +2 · 1 citation
Computer Science · #Caching and Content Delivery #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Information Theory (cs.IT) #Mobile Ad Hoc Networks
paper · pdf · doi:10.48550/arxiv.1701.07115
openalex publication_date 2017/01/24 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
Coded caching is a problem where encoded broadcasts are used to satisfy users\nrequesting popular files and having caching capabilities. Recent work by\nMaddah-Ali and Niesen showed that it is possible to satisfy a scaling number of\nusers with only a constant number of broadcast transmissions by exploiting\ncoding and caching. Unfortunately, all previous schemes required the splitting\nof files into an exponential number of packets before the significant coding\ngains of caching appeared. The question of what can be achieved with polynomial\nsubpacketization (in the number of users) has been a central open problem in\nthis area. We resolve this problem and present the first coded caching scheme\nwith polynomial (in fact, linear) subpacketization. We obtain a number of\ntransmissions that is not constant, but can be any polynomial in the number of\nusers with an exponent arbitrarily close to zero. Our central technical tool is\na novel connection between Ruzsa-Szem 'eredi graphs and coded caching.\n