A Hypergraph based lower bound on Pliable Index Coding based on Nested Side-Information Sets
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914194897502208 |
|---|---|
| author | B., Tulasi Sowjanya Krishnan, Prasad |
| author_facet | B., Tulasi Sowjanya Krishnan, Prasad |
| contents | In pliable index coding (PICOD), a number of clients are connected via a noise-free broadcast channel to a server which has a list of messages. Each client has a unique subset of messages at the server as side-information, and requests for any one message not in the side-information. A PICOD scheme of length $\ell$ is a set of $\ell$ encoded transmissions broadcast from the server such that all clients are satisfied. Finding the optimal (minimum) length of PICOD and designing PICOD schemes that have small length are the fundamental questions in PICOD. In this paper, we present a new lower bound for the optimal PICOD length using a new structural parameter called the nesting number, denoted by $η(\ch)$ associated with the hypergraph $\ch$ that represents the PICOD problem. While the nesting number bound is not stronger than previously known bounds, it can provide some computational advantages over them. Also, using the nesting number bound, we obtain novel lower bounds for some PICOD problems with special structures, which are tight in some cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_01539 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Hypergraph based lower bound on Pliable Index Coding based on Nested Side-Information Sets B., Tulasi Sowjanya Krishnan, Prasad Information Theory In pliable index coding (PICOD), a number of clients are connected via a noise-free broadcast channel to a server which has a list of messages. Each client has a unique subset of messages at the server as side-information, and requests for any one message not in the side-information. A PICOD scheme of length $\ell$ is a set of $\ell$ encoded transmissions broadcast from the server such that all clients are satisfied. Finding the optimal (minimum) length of PICOD and designing PICOD schemes that have small length are the fundamental questions in PICOD. In this paper, we present a new lower bound for the optimal PICOD length using a new structural parameter called the nesting number, denoted by $η(\ch)$ associated with the hypergraph $\ch$ that represents the PICOD problem. While the nesting number bound is not stronger than previously known bounds, it can provide some computational advantages over them. Also, using the nesting number bound, we obtain novel lower bounds for some PICOD problems with special structures, which are tight in some cases. |
| title | A Hypergraph based lower bound on Pliable Index Coding based on Nested Side-Information Sets |
| topic | Information Theory |
| url | https://arxiv.org/abs/2511.01539 |