A unified Ruzsa-Szemerédi framework for finite-length coded caching

Abstract

We review existing work on efficient schemes for finite length coded caching. The coded caching problem studies efficient ways of broadcasting in a noiseless wireless network where each user is equipped with cache of size M files and has possibly distinct demands from a library of N files. The problem is to jointly design the cache content and the transmission protocol such that, irrespective of the demand pattern, every user can decode their demanded file. Schemes were proposed that are almost information theoretically optimal and ensure that at most N/M transmissions are needed in the worst case. However, to achieve this, files need to be split into exponentially many packets that increases complexity of encoding, decoding and delay. In recent years, search for schemes that are efficient in terms of file size has gathered considerable interest. We outline a class of coded caching schemes based on Ruzsa-Szemerédi constructions. All existing schemes can be cast in this framework. We demonstrate this by casting a few existing schemes, arrived at using seemingly disparate ideas, in the Ruzsa-Szemerédi framework. We also discuss remaining open problems in tackling this important practical issue.