TY - JOUR
T1 - Nonlinear index coding outperforming the linear optimum
AU - Lubetzky, Eyal
AU - Stav, Uri
N1 - Funding Information:
Manuscript received November 22, 2007; revised May 07, 2009. Current version published July 15, 2009. The work of E. Lubetzky was supported in part by a Charles Clore Foundation Fellowship. The material in this paper was presented in part at the 48th IEEE Foundation of Computer Science Conference, Providence, RI, October 2007. E. Lubetzky is with the Theory Group, Microsoft Research, Redmond, WA 98052 USA (e-mail: eyal@microsoft.com). U. Stav is with the School of Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel-Aviv University, Tel-Aviv, Ramat–Aviv 69978, Israel (e-mail: uristav@tau.ac.il). Communicated by W. Szpankowski, Associate Editor for Source Coding. Digital Object Identifier 10.1109/TIT.2009.2023702
PY - 2009
Y1 - 2009
N2 - The following source coding problem was introduced by Birk and Kol: a sender holds a word χ ∈ {0, 1}n, and wishes to broadcast a codeword to n receivers, R1,..., Rn. The receiver Ri is interested in xi, and has prior side information comprising some subset of the n bits. This corresponds to a directed graph G on n, where ij is an edge iff Ri knows the bit xj. An index code for G is an encoding scheme which enables each Ri to always reconstruct xi, given his side information. The minimal word length of an index code was studied by Bar-Yossef, Birk, Jayram, and Kol (FOCS'06). They introduced a graph parameter, minrk2(G), which completely characterizes the length of an optimal linear index code for G. They showed that in various cases linear codes attain the optimal word length, and conjectured that linear index coding is in fact always optimal. In this work, we disprove the main conjecture of Bar-Yossef, Birk, Jayram, and Kol in the following strong sense: for any ε > 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 n1-c, and yet a nonlinear index code for G has aword length of nc. 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 (G).
AB - The following source coding problem was introduced by Birk and Kol: a sender holds a word χ ∈ {0, 1}n, and wishes to broadcast a codeword to n receivers, R1,..., Rn. The receiver Ri is interested in xi, and has prior side information comprising some subset of the n bits. This corresponds to a directed graph G on n, where ij is an edge iff Ri knows the bit xj. An index code for G is an encoding scheme which enables each Ri to always reconstruct xi, given his side information. The minimal word length of an index code was studied by Bar-Yossef, Birk, Jayram, and Kol (FOCS'06). They introduced a graph parameter, minrk2(G), which completely characterizes the length of an optimal linear index code for G. They showed that in various cases linear codes attain the optimal word length, and conjectured that linear index coding is in fact always optimal. In this work, we disprove the main conjecture of Bar-Yossef, Birk, Jayram, and Kol in the following strong sense: for any ε > 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 n1-c, and yet a nonlinear index code for G has aword length of nc. 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 (G).
KW - Index coding
KW - Linear and nonlinear source coding
KW - Ramsey constructions
UR - http://www.scopus.com/inward/record.url?scp=68249135283&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=68249135283&partnerID=8YFLogxK
U2 - 10.1109/TIT.2009.2023702
DO - 10.1109/TIT.2009.2023702
M3 - Article
AN - SCOPUS:68249135283
SN - 0018-9448
VL - 55
SP - 3544
EP - 3551
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 8
ER -