  Coded caching is a problem where encoded broadcasts are used to satisfy users
requesting popular files and having caching capabilities. Recent work by
Maddah-Ali and Niesen showed that it is possible to satisfy a scaling number of
users with only a constant number of broadcast transmissions by exploiting
coding and caching. Unfortunately, all previous schemes required the splitting
of files into an exponential number of packets before the significant coding
gains of caching appeared. The question of what can be achieved with polynomial
subpacketization (in the number of users) has been a central open problem in
this area. We resolve this problem and present the first coded caching scheme
with polynomial (in fact, linear) subpacketization. We obtain a number of
transmissions that is not constant, but can be any polynomial in the number of
users with an exponent arbitrarily close to zero. Our central technical tool is
a novel connection between Ruzsa-Szem\'eredi graphs and coded caching.
