{"id":{"repo_id":"uic","oai_identifier":"oai:figshare.com:article/31451032"},"canonical_url":"https://search.dev.ndltd.org/etd/uic/oai:figshare.com:article/31451032","repository":{"repo_id":"uic","name":"University of Illinois - Chicago","base_url":"https://api.figshare.com/v2/oai"},"display":{"title":"A Linear Programming Framework for Converse Bounds in Coded Caching with Linear Placement","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Niccolò Brembilla (23291290)"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-12-01T00:00:00Z","date_published":"2025-12-01T00:00:00Z","updated_at":"2026-07-27T21:34:19Z","subjects":["Computer Science","Linear Programming","Information Theory"],"languages":[],"rights":["In Copyright"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://doi.org/10.25417/uic.31451032.v1","outbound_label":"DOI","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Niccolò Brembilla (23291290)"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-12-01T00:00:00Z"]},{"key":"dc:relation","label":"Dc Relation","values":["https://figshare.com/articles/thesis/A_Linear_Programming_Framework_for_Converse_Bounds_in_Coded_Caching_with_Linear_Placement/31451032"]},{"key":"dc:type","label":"Dc Type","values":["Text","Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science","Linear Programming","Information Theory"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["10.25417/uic.31451032.v1"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:title","label":"Title","values":["A Linear Programming Framework for Converse Bounds in Coded Caching with Linear Placement"]}]}],"canonical_facts":{"dc:creator":["Niccolò Brembilla (23291290)"],"dc:date":["2025-12-01T00:00:00Z"],"dc:description":["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."],"dc:identifier":["10.25417/uic.31451032.v1"],"dc:relation":["https://figshare.com/articles/thesis/A_Linear_Programming_Framework_for_Converse_Bounds_in_Coded_Caching_with_Linear_Placement/31451032"],"dc:rights":["In Copyright"],"dc:subject":["Computer Science","Linear Programming","Information Theory"],"dc:title":["A Linear Programming Framework for Converse Bounds in Coded Caching with Linear Placement"],"dc:type":["Text","Thesis"]},"updated_at":"2026-07-27T21:34:19Z"}