Coded caching with linear coded placement: a linear programming framework for converse bounds

Coded caching is a communication strategy that combines local storage with coding techniques to reduce the data transmitted over a shared network. In its standard formulation, a server with a library of N files serves K users, each equipped with a cache of size M. The objective is to design placement and delivery strategies that minimize the worst-case broadcast rate. While uncoded placement strategies are well understood, in the small-memory regime (M ≪ N) achieving optimal performance often requires coded placements, whose theoretical limits remain poorly characterized. This thesis develops a computational framework for deriving converse bounds in coded caching with coded placement. Converse bounds, which describe the fundamental limits of performance, can be expressed as linear programs (LPs) using information-theoretic inequalities, but the doubly exponential growth of the problem in K and N makes them intractable even for small instances. The proposed framework in this thesis, implemented in C++, overcomes this challenge by exploiting problem symmetries and other techniques to reduce the number of variables and constraints. It integrates Shannon and non-Shannon inequalities, employs OpenMP for parallelization, and leverages Gurobi for efficient optimization. This approach breaks previous scalability barriers and enables the computation of converse bounds for arbitrary (K,N), providing a powerful tool to explore the memory-rate tradeoff in coded caching.

Il coded caching è una strategia di comunicazione che combina lo storage locale con tecniche di coding per ridurre la quantità di dati trasmessi su un canale condiviso. Nel problema generale si considera un server che ospita una libreria di N file e serve K utenti, ognuno con una cache di capacità M , tramite un canale condiviso. L’obiettivo è progettare strategie di posizionamento e consegna che minimizzino il tasso di trasmissione nel caso peggiore. Mentre le strategie con placement non codificato sono ben conosciute, nel regime di piccola memoria (M ≪ N ) ottenere prestazioni ottimali richiede spesso placement codificati, i cui limiti teorici non sono ancora ben compresi. Questa tesi propone un framework computazionale per derivare automaticamente limiti fondamentali (converse bounds) nel coded caching con placement codificato. Tali limiti possono essere formulati come programmi lineari (LP) basati su disuguaglianze della teoria dell’informazione, ma la crescita doppiamente esponenziale in K e N del problema lo rende intrattabile anche per istanze piccole. Il framework proposto in questa tesi, implementato in C++, affronta questa sfida sfruttando simmetrie e altre tecniche per ridurre il numero di variabili e vincoli. La nostra soluzione integra nel problema disuguaglianze di Shannon e non-Shannon, utilizza OpenMP per il parallelismo e si affida a Gurobi per l’ottimizzazione della soluzione. L’approccio supera le precedenti barriere di scalabilità e permette di calcolare bound per coppie arbitrarie (K, N ), offrendo uno strumento potente per studiare il compromesso memoria–tasso di trasmissione nel coded caching.