PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-linear index coding outperforming the linear optimum

Eyal Lubetzky, Uri Stav

arXiv:0806.1919v1cs.ITmath.IT

TL;DR

The paper addresses whether linear index codes always achieve optimal length, a conjecture motivated by cases where minrk2(G) characterizes the optimal linear length. The authors extend Alon’s Ramsey-graph construction and use gaps between minrank parameters over fields of distinct characteristics. For these n-vertex graphs, any linear index code requires a word length of n1−o(1) bits, while a given index code utilizes words only no(1) bits long.

  • Problem

    The paper addresses whether linear index codes always achieve optimal length, a conjecture motivated by cases where minrk2(G) characterizes the optimal linear length.

    Source: §1 · p. 1, §1.2 · p. 4

  • Method

    The authors extend Alon’s Ramsey-graph construction and use gaps between minrank parameters over fields of distinct characteristics.

    Source: §1.2 · p. 4, §1.3 · p. 5

  • Results

    For these n-vertex graphs, any linear index code requires a word length of n1−o(1) bits, while a given index code utilizes words only no(1) bits long.

    Source: §5 · p. 15

  • Takeaways & Limitations

    These constructions disprove the conjecture that linear index coding is always optimal.

    Source: §1.2 · p. 4, §5 · p. 15

    The model assumes each receiver requests exactly one data block and each data block is requested only once.

    Source: §4 · p. 12

Abstract

from arXiv · show

The following source coding problem was introduced by Birk and Kol: a sender holds a word $x\in\{0,1\}^n$, and wishes to broadcast a codeword to $n$ receivers, $R_1,...,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 $i j$ 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, $\minrk_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^\epsilon$. 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)$.

1 Introduction

The introduction frames index coding as broadcasting bits to receivers with graph-encoded side information, then challenges the conjecture that linear codes always attain the shortest length.

1 Introduction

  • Each receiver seeks one bit of a sender’s word and uses prior side information; a directed graph records which bits each receiver knows.The paper studies the setting where the sender knows the receivers’ side information and each receiver wants only its own bit.Source: §1 · pp. 1–2

1.1 Definitions, notations and background

  • The parameter minrk2(G) characterizes optimal linear index-code length, and prior results for several graph families motivated the conjecture that linear coding is always optimal.The cited work also established cases where linear codes are optimal and an information-theoretic lower bound based on maximal acyclic induced subgraphs.Source: §1 · pp. 2–3

1.2 New results

  • For every ε > 0 and sufficiently large n, an explicit undirected n-vertex graph requires at least n^(1−ε) bits linearly but admits a nonlinear index code of at most n^ε bits.This strictly improves on the minrk2(G) bound and disproves the conjecture that linear index coding is always optimal.Source: §1.2 · p. 4
  • For any fixed collection of finite fields, the paper constructs graphs with minrank at most n^ε over one field and at least n^(1−ε) over fields of a distinct characteristic.The paper also reports that a related upper bound is not always tight and gives a minrank-to-Lovász-ϑ separation of roughly √n.Source: §1.2 · p. 5
  • The paper also proposes natural extensions for repeated requests, multiple transmission rounds, and larger transmission alphabets, relating these models to ℓ(G) and minrk(G).Source: §1.2 · p. 5

1.3 Techniques

  • The construction extends Alon’s variant of the Frankl–Wilson Ramsey construction to prime powers, allowing sufficiently large powers of distinct primes to replace the requirement that both primes be large.Variants support the multiple-field results, alongside arguments from linear algebra, number theory, and graph-capacity ideas.Source: §1.3 · p. 5

2 Linear index codes over higher-order fields

This section constructs graphs where linear index codes over a higher-order field outperform codes over GF(2), and gives a bound converting finite-field minrank into an index-code length. The construction extends Ramsey-style graph methods to produce contrasting minrank behavior across fields.

2.2 Proof of Proposition 2.1

  • For any representing matrix A over a finite field F, the number of possible Ax values gives an index-code length bound, and its rank yields a linear code of the same length.The bound is ℓ(G) ≤ ⌈minrk_F(G) log2 |F|⌉; an optimal linear code over F has length ⌈minrk_F(G) log2 |F|⌉.Source: §2.1 · p. 6, §2.2 · p. 7

2.3 Proof of Proposition 2.2

  • An explicit family of graphs is constructed for two finite fields of distinct characteristics, with representing matrices over both fields obtained from inclusion matrices.The construction uses P = M_(p^k−1)M_(p^k−1)^T and Q = M_(q^l−1)M_(q^l−1)^T to represent the graph over GF(p) and GF(q), respectively.Source: §2.1 · p. 6, §2.3 · pp. 8–9

2.1 Proof of Theorem 1.1

  • For every ε > 0 and sufficiently large n, the constructed graph forces every linear index code over GF(2) to have word length at least n^(1−ε) bits.The construction applies Proposition 2.2 with F = GF(p) and K = GF(2), where p > 2 is any fixed odd prime.Source: §2.1 · pp. 6–7

2.3 Proof of Proposition 2.2

  • The proof extends the construction from distinct prime fields to prime-power fields by relating their minranks, and compares its set-intersection construction with Alon’s and Frankl–Wilson’s Ramsey constructions.For prime p and integer k, minrk_p(G) ≤ k minrk_(p^k)(G), while minrk_(p^k)(G) ≤ minrk_p(G).Source: §2.3 · pp. 9–10

3 Outperforming linear index codes over multiple fields

This section extends the graph construction to multiple fields and proves bounds by combining graph instances. The argument uses disjoint unions and product-graph properties to relate code lengths and minranks.

3.1 Proof of Theorem 1.2

  • The proof of Theorem 1.2 applies Proposition 2.2 over GF(2) and GF(3), then uses a disjoint union to combine graph instances.The selected graph has minrk_2(G) ≤ n^(ε/2), as specified by the construction parameters.Source: §3.1 · p. 11, §3.2 · p. 11
  • Partitioning a graph into induced subgraphs gives ℓ(G) ≤ the sum of their individual index-code lengths, which is used to bound the code length of the combined construction.The proof also uses an independent set in G × G and the fact that this product is an induced subgraph of H × H to obtain a lower bound on c(H).Source: §3.1 · p. 11

3.2 Proof of Proposition 1.3

  • For Proposition 1.3, the graphs built for fields of distinct characteristics are combined by disjoint union; the resulting adjacency matrix is block diagonal, and each field’s minrank is at least that of its corresponding component.The proof assumes pairwise distinct characteristics for the fields after using minrk_(p^e)(G) ≤ minrk_(p^d)(G) when e > d.Source: §3.2 · p. 11

4 The problem definition revisited

This section revisits restrictions in the basic index-coding model and treats larger alphabets, multiple rounds, and repeated requests. It gives reductions and bounds for these settings, including an example where joint transmissions save bits.

4 The problem definition revisited

  • The basic model restricts each receiver to one requested block, each block to one request, and each block to one bit; the section reconsiders the latter two restrictions.The one-request-per-receiver restriction can be handled by replacing a user requesting multiple blocks with multiple users sharing that user's side information.Source: §4 · pp. 11–12

4.1 Larger alphabet and multiple rounds

  • For t rounds with the same side-information graph, the problem reduces to ordinary index coding on the t-blow-up G[t], and ℓ(G[t]) ≤ t·ℓ(G).When an undirected graph satisfies ℓ(G) = α(G), including perfect graphs, the bound is tight: ℓ(G[t]) = t·ℓ(G).Source: §4.1 · p. 12
  • When side-information graphs vary by round, the generalization reduces to ordinary index coding on a graph formed from the round-specific graphs.For two transitive tournaments with reversed edges, separate transmissions cost 2n bits, while the combined instance has optimal length n+1.Source: §4.1 · p. 13
  • With multiple rounds, a unified transmission can save communication: two separate rounds in the example require two bits each, while the joint transmission lets both receivers recover their missing bits.For the reversed transitive-tournament pair, the individual lengths sum to 2n, but the combined length is n+1.Source: §4.1 · pp. 13–14

4.2 Shared requests

  • When multiple users may request the same bit, a binary m × n matrix represents side information, and its minimum representing rank gives the optimal linear-code length.Theorem 4.4 also extends the stated upper bounds for arbitrary index codes to this setting.Source: §4.2 · p. 14
  • For repeated requests, the paper defines user-based graphs Gind and Gcl, distinguishing users requesting the same bit as independent sets or cliques, respectively.The claim based on these graphs supplies additional bounds on ℓ(P4).Source: §4.2 · p. 14

5 Concluding remarks and open problems

The paper constructs graphs where nonlinear index coding is dramatically shorter than any linear code, extending the separation across fields and related coding settings. The concluding remarks identify open questions about the gap between coding parameters and coding multiple data blocks.

5 Concluding remarks and open problems

  • Linear codes require n^(1-o(1)) bits on the constructed graphs, while the given nonlinear codes use only n^(o(1)) bits.This disproves the conjecture that linear index coding is always optimal.Source: §5 · p. 15
  • Higher-order-field linear codes outperform GF(2) codes on the constructed graphs, and a variant makes linear codes over every field suboptimal.The construction extends Alon’s variant of the Frankl–Wilson Ramsey construction.Source: §5 · p. 15
  • Tight bounds on ℓ(G) for general graphs remain an open problem.Source: §5 · p. 15
  • The construction yields a minrk2(G)/ℓ(G) ratio of n/exp(O(√(log n log log n))), while an e^Theta(n) gap remains an open target.The authors note that reaching the larger gap may require a different approach or substantially improved Ramsey constructions.Source: §5 · p. 15
  • For dynamically changing side-information graphs, transmitting t binary words together can save communication compared with transmitting them independently.The paper also shows that more general index-coding scenarios can be reduced to its main problem.Source: §5 · p. 15
  • For b-bit blocks on a fixed graph, coding each bit separately uses b·ℓ(G) bits, but this need not be optimal; subsequent work answered the possibility question affirmatively.The discussion focuses on large blocks with b ≫ n.Source: §5 · p. 15
Loading 0806.1919v1…