Non-Linear Index Coding Outperforming the Linear Optimum

The following source coding problem was introduced by Birk and Kol: a sender holds a word x epsi {0,1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> , and wishes to broadcast a codeword to n receivers, R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> ,..., R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> middot. The receiver R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> is interested in x;, and has prior 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 <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> knows the bit x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j</sub> . An index code for G is an encoding scheme which enables each R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> to always reconstruct Xj, given his side information. The minimal word length of an index code was studied by Bar-Yossef Birk, Jay ram and Kol. Thev introduced a graph parameter, minrk <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> (G), which completely characterizes the length of an optimal linear index code for G. The authors of (Z. Bar-Yossef, 2006) 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 (Z. Bar-Yossef, 2006) in the following strong sense: for any epsiv > 0 and sufficiently large n, there is an n-vertex graph G so that evety linear index code for G requires codewords of length at least n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1-epsiv</sup> and yet a non-linear index code for G has a word length of n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">epsiv</sup> . This is achieved by an explicit construction, which extends Alon's variant of the celebrated Ramsey construction of Frankl and Wilson.