Nonlinear Index Coding Outperforming the Linear Optimum

DOI10.1109/TIT.2009.2023702MaRDI QIDQ4975953zbMATH OpenOpenAlexFDO

Authors Eyal Lubetzky, Uri Stav

Publication date 8 August 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0806.1919

Mathematics Subject Classification ID

Source coding (94A29)

Abstract: The following source coding problem was introduced by Birk and Kol: a sender holds a word $xin{0,1}^n$, and wishes to broadcast a codeword to $n$ receivers, $R_1,\mathrm{...},R_n$. The receiver $R_i$ is interested in $x_i$, and has prior emph{side information} comprising some subset of the $n$ bits. This corresponds to a directed graph $G$ on $n$ vertices, where $ij$ is an edge iff $R_i$ knows the bit $x_j$. An emph{index code} for $G$ is an encoding scheme which enables each $R_i$ to always reconstruct $x_i$, given his side information. The minimal word length of an index code was studied by Bar-Yossef, Birk, Jayram and Kol (FOCS 2006). They introduced a graph parameter, $minr{k}_2(G)$, which completely characterizes the length of an optimal emph{linear} index code for $G$. The authors of BBJK showed that in various cases linear codes attain the optimal word length, and conjectured that linear index coding is in fact emph{always} optimal. In this work, we disprove the main conjecture of BBJK in the following strong sense: for any $epsilon>0$ and sufficiently large $n$, there is an $n$-vertex graph $G$ so that every linear index code for $G$ requires codewords of length at least $n^{1-epsilon}$, and yet a non-linear index code for $G$ has a word length of $n^{e}psilon$. This is achieved by an explicit construction, which extends Alon's variant of the celebrated Ramsey construction of Frankl and Wilson. In addition, we study optimal index codes in various, less restricted, natural models, and prove several related properties of the graph parameter $minrk(G)$.

Cited in

(13)

• The minrank of random graphs over arbitrary fields
• Optimal Index Codes With Near-Extreme Rates
• A bound on the Shannon capacity via a linear programming variation
• A Linear Encoding Approach to Index Assignment in Lossy Source-Channel Coding
• The minrank of random graphs
• On minrank and the Lovász theta-function
• Linear Programming Approximations for Index Coding
• Bounding the Optimal Rate of the ICSI and ICCSI problem
• Linear index coding via semidefinite programming
• Linear index coding via semidefinite programming
• Local orthogonality dimension
• L-systems and the Lovász number
• The hat guessing number of graphs

This page was built for publication: Nonlinear Index Coding Outperforming the Linear Optimum

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4975953)