Symmetric uncoded caching schemes with low subpacketization levels
Caching is a commonly used technique in content-delivery networks which aims to deliver information from hosting servers to users in the most efficient way. In 2014, Maddah-Ali and Niessen formulated caching into a formal information theoretic problem and it has gained a lot of attention since then. It is known that the caching schemes proposed by Ali-Niesen and Yu et. al. are optimal, that is, they require the least number of transmissions from the server to satisfy all users' demands. However for these schemes to work, each file needs to be partitioned into $F^*$ subfiles ($F^*$ is called the subpacketization level of files) with $F^*$ growing exponentially in the number $K$ of users. As a result, it is problematic to apply these schemes in practical situations, where $K$ tends to be very large. There rise the following questions: (1) are there optimal schemes in which each file is partitioned into $F$ subfiles, where $F$ is not exponential, say polynomial for example, in $K$? (2) if the answer to this question is no, is there a near-optimal scheme, a scheme which is as asymptotically good as the one in \cite{ali1,yu}, with $F$ polynomial in $K$? Both these questions are open. Our main contribution in this paper is to provide answers to above questions. Firstly, we prove that under some mild restriction on user's cache rate, there are no optimal schemes with $F$ smaller than $F^*$. Moreover, we give necessary and sufficient conditions for the existence of optimal schemes in this case. Secondly, we provide an affirmative answer to the second question raised above by an explicit construction and a detailed performance analysis.