A Linear Programming Framework for Converse Bounds in Coded Caching with Linear Placement

In the coded caching model, a server stores a library of N files and serves K users over a shared broadcast link. Each user has a cache of size M files. The goal is to design placement and delivery strategies that minimize the worst-case broadcast rate across all possible user demands. While uncoded placements are well understood, it is known that in the small-memory regime, when M ≪ N, optimal performance often requires coded placements. However, the theoretical understanding of such strategies remains limited. This thesis aims to close this gap by developing a computational framework for deriving converse bounds, which characterize the fundamental limits of coded caching with coded placement. These bounds can be formulated as linear programs (LPs) using information-theoretic inequalities, but their size grows doubly exponentially with K and N, making even small instances (e.g., 3 users and 3 files) challenging to solve. To address this, we introduce a scalable C++ framework that automates LP construction and solution, leveraging both Shannon and non-Shannon inequalities. By exploiting problem symmetries and sparsity, we significantly reduce the number of variables and constraints. The implementation uses OpenMP for parallelism and integrates Gurobi for efficient optimization. Our tool enables automated computation of converse bounds for arbitrary (K, N) values, overcoming previous scalability barriers and providing a powerful platform to explore the memory-rate tradeoff in coded caching.

Author dc:creator

• Niccolò Brembilla (23291290)

• Computer Science
• Linear Programming
• Information Theory

Statement dc:rights

• In Copyright

DOI dc:identifier

https://doi.org/10.25417/uic.31451032.v1

OAI identifier oai:identifier

oai:figshare.com:article/31451032