PaperlayerView exact revision on arXiv

Source-linked AI summary

Lexicographic products and the power of non-linear network coding

Anna Blasiak, Robert Kleinberg, Eyal Lubetzky

arXiv:1108.2489v1cs.ITmath.CO

TL;DR

The paper addresses unknown or small gaps between network-coding and index-coding parameters. It combines linear programs with hypergraph lexicographic products and matroid-index-coding connections to amplify separations, obtaining polynomial gaps including between non-linear and linear network-coding rates.

  • Problem

    General network-coding rates and worst-case gaps between coding-theoretic and combinatorial parameters remain difficult to compute or approximate, with some prior gaps only constant-sized or unknown.

    Source: §1 · pp. 1–2

  • Method

    The paper combines information-theoretic linear programs, dual-solution composition, hypergraph lexicographic products, and matroid-index-coding constructions.

    Source: §1.1 · p. 3

  • Results

    The paper obtains polynomial separations, including a non-linear network-coding rate Ω(n^ε) times the linear rate and β(G) at least Ω(n^δ) times α(G), with δ = 1 −2 log5(2) ≈0.139.

    Source: §1.1 · pp. 3–4

  • Takeaways & Limitations

    Lexicographic products provide a general recipe for amplifying linear-programming lower bounds into polynomial gaps among coding and combinatorial parameters.

    Source: §1.1 · p. 3

    The linear-programming framework requires a tight homomorphic constraint schema, and the paper also considers characteristic-specific linear-code constraints.

    Source: §1.1 · p. 3, §6.1 · p. 16

Abstract

from arXiv · show

We introduce a technique for establishing and amplifying gaps between parameters of network coding and index coding. The technique uses linear programs to establish separations between combinatorial and coding-theoretic parameters and applies hypergraph lexicographic products to amplify these separations. This entails combining the dual solutions of the lexicographic multiplicands and proving that they are a valid dual of the product. Our result is general enough to apply to a large family of linear programs. This blend of linear programs and lexicographic products gives a recipe for constructing hard instances in which the gap between combinatorial or coding-theoretic parameters is polynomially large. We find polynomial gaps in cases in which the largest previously known gaps were only small constant factors or entirely unknown. Most notably, we show a polynomial separation between linear and non-linear network coding rates. This involves exploiting a connection between matroids and index coding to establish a previously unknown separation between linear and non-linear index coding rates. We also construct index coding problems with a polynomial gap between the broadcast rate and the trivial lower bound for which no gap was previously known.

1 Introduction

The paper develops a linear-programming and lexicographic-product technique for amplifying gaps among network-coding and index-coding parameters. It applies the framework to obtain polynomial separations, including between linear and non-linear network coding rates and between broadcast rate and independence number.

1. Introduction

  • The work addresses limited general understanding of network-coding rates, where restricted coding models and graph parameters provide bounds whose worst-case approximation factors were previously unknown.Network coding asks for the maximum information rate through a capacitated network, but general computation and approximation remain poorly understood.Source: §1 · p. 1
  • The method uses index coding as a bridge between network coding, graph parameters, and matroid-based information inequalities.Index coding is essentially the one-finite-capacity-edge case of network coding, and matroid realizability characterizes linear solvability of corresponding index-coding problems.Source: §1 · p. 2

1.1 Contributions

  • The technique combines linear programs with hypergraph lexicographic products, combining dual solutions so lower bounds become supermultiplicative under products.The framework applies beyond standard entropy programs to linear programs built from tight homomorphic constraint schemas.Source: §1.1 · p. 3
  • Matroid non-realizability yields characteristic-specific inequalities that separate the best linear and non-linear index-coding rates, which are then amplified by lexicographic products.The construction uses the Fano and non-Fano matroids and transforms violations of their rank functions into valid linear-code inequalities.Source: §1.1 · p. 3
  • A family of network-coding instances has non-linear rate Ω(n^ε) times larger than linear rate for some fixed ε > 0.Before this work, the largest known non-linear versus vector-linear network-coding gap was a factor of 11, while no index-coding separation was known for these parameters.Source: §1.1 · pp. 3–4
  • An explicit family of index-coding instances with n messages satisfies β(G) ≥ Ω(n^δ) times α(G), where δ = 1 −2 log5(2) ≈0.139.The construction uses lexicographic products to amplify a 5-cycle gap, whose independence number α equals 2, yielding a polynomially growing β/α ratio.Source: §1.1 · p. 4

2 Definitions

Index coding models receivers that use broadcast information and side-information to recover demanded messages, with asymptotic broadcast rate as the main quantity. Lexicographic products combine instances while preserving a multiplicative upper bound on broadcast rate.

Index coding

  • Index coding uses a directed hypergraph whose vertices are messages and whose hyperedges represent receivers, side-information sets, and demanded messages.Each receiver decodes its demanded message from the public encoding and the messages in its side-information set.Source: §2 · p. 4

Broadcast rate

  • The broadcast rate β(G) is the asymptotic number of public-channel bits per input bit for long messages.The finite-message quantity β_t(G) is normalized by message length, with the limit used for long-message analysis.Source: §2 · p. 4

Lexicographic products

  • The lexicographic product G • F replaces each vertex of G with a copy of F and forms receiver tails from the outer and inner side-information sets.Its vertices are pairs from V(G) × V(F), and G•n denotes the n-fold product.Source: §2 · p. 5
  • β(G • F) ≤ β(G)β(F), achieved by applying an optimal code for F within each outer vertex and then an optimal code for G to the resulting messages.The inner code produces intermediate messages, which the outer code broadcasts; receivers decode in that order.Source: §2 · p. 5

3 Linear programming

The paper formulates broadcast-rate lower bounds as linear programs whose validity follows from entropy inequalities and whose structure supports lexicographic-product amplification. Tight homomorphic constraint schemas let dual solutions from two factors combine into a feasible product dual with multiplicative objective value.

LP formulation

  • The LP value b(G) is a lower bound on the broadcast rate β(G), with submodularity constraints providing a concrete valid instantiation.The primal assigns entropy-based variables to message subsets, while the constraint matrix can incorporate additional universally valid or model-specific inequalities.Source: §3 · pp. 6–7

Constraint schemas

  • A constraint schema assigns matrices to finite index sets and maps constraints under Boolean lattice homomorphisms; tightness requires A(I)1 = A(I)1i = 0.Submodularity is an example, encoding zS + zT ≥ zS∩T + zS∪T.Source: §3 · pp. 6–7

Product theorem

  • For a tight homomorphic constraint schema, the LP optimum satisfies ρ(G • F) ≥ ρ(G)ρ(F).The product proof lifts the dual solution for F through maps hST and the dual solution for G through g.Source: §3 · pp. 8–9
  • The lifted pair (ξG•F, ηG•F) is feasible because homomorphicity transfers the factor dual constraints to the product.The construction contains one lifted copy of F’s dual for each outer subset pair and one lifted copy of G’s dual.Source: §3 · pp. 9–10
  • The dual objective of the lifted solution is at least ρ(G)ρ(F), completing the supermultiplicativity proof under lexicographic products.The objective comparison uses the product’s closure structure and the factor quantities d(S,T) and d(X,Y).Source: §3 · pp. 10–11

4 Separation between α and β

A constant separation between the independence number α and broadcast rate β on the 5-cycle becomes polynomial under lexicographic powers. The resulting graphs have n = 5^k vertices, α = n^log5(2), and β at least n^(1−log5(2)).

Base instance

  • The 5-cycle satisfies β(C5) > α(C5), providing the constant gap that initiates the construction.The lower bound follows from the LP method in Theorem 3.1.Source: §4 · p. 11

Amplification

  • Lexicographic powers amplify the 5-cycle gap because β is supermultiplicatively lower-bounded by the LP framework while independence number is multiplicative.The construction applies Theorem 3.4 to C5^k.Source: §4 · pp. 11–12
  • n^(1−log5(2)) ≤ β(C5^k) for graphs with n = 5^k vertices, while α(C5^k) = n^log5(2).Thus the construction gives a polynomial separation between broadcast rate and the independence-number lower bound.Source: §4 · p. 12

5 Matroids and index coding

The paper maps matroids to index-coding instances so that matroid rank and representability govern combinatorial and linear coding parameters. This connection supplies LP separations and links under-representability over a field to scalar linear index-coding rate.

Matroid-to-index-coding mapping

  • The matroid-associated index-coding problem GM has messages E and receivers for dependencies satisfying r(S) = r(S ∪{x}).The construction is designed to capture the matroid’s dependency structure in receiver side-information.Source: §5 · p. 12

LP value

  • For every matroid M, the LP lower-bound value satisfies b(GM) = |E| − r(E).A feasible primal solution uses zS = r(S) + |E| − r(E).Source: §5 · p. 12

Linear coding and representability

  • A matroid under-representable in d dimensions over F yields λF_1(GM) ≤ n − d, with equality when d = r(E).If M is representable over F, then λF(GM) = β(GM) = n − r(E).Source: §5 · p. 13
  • Under-representations and scalar linear codes correspond through matrices whose kernels and row spaces encode receiver dependencies.A matrix spanning the kernel of a linear encoding matrix under-represents the matroid, and conversely an under-representation produces a valid encoding matrix.Source: §5 · pp. 13–14

LP separation

  • If a constraint matrix A satisfies A1 = 0 but violates the matroid rank vector, the associated LP value is strictly greater than |E| − r(E).The proof constructs a dual solution supported on a violated constraint row.Source: §5 · p. 14

6 Separation between linear and non-linear rates

This section develops constraint-schema methods and lexicographic-product constructions to separate and amplify linear and non-linear index-coding rates. It establishes instances with non-linear broadcast rate 16^n and a field-dependent linear-rate lower bound of (16+ε)^n.

6 Separation between linear and non-linear rates

  • β(G•n) = 16n, whereas λ(G•n) ≥ (16 + ε)n for every n and some ε > 0.The construction takes G = GF • GN and uses lexicographic products to produce and amplify the separation.Source: §6 · p. 15
  • The proof lower-bounds linear rates by extending LP B with characteristic-specific dimension constraints derived from the Fano and non-Fano matroids.These constraints show that the product cannot be matched by a single linear code, although combining linear codes over F2 and F3 achieves the non-linear rate.Source: §6 · p. 15

6.1 Linear codes over fields of characteristic two

  • In characteristic two, a 27-dimensional vector Λeven gives, for any seven subspaces, the inequality dim(V110, V101, V011) ≤ 2 dim(V111).Source: §6.1 · p. 17

6.2 Linear codes over fields of odd characteristic

  • The odd-characteristic development provides analogous inequalities for fields of odd characteristic, extending the characteristic-specific LP approach beyond the even-characteristic case.The supplied passage introduces these analogues but does not state their resulting numerical bound.Source: §6.2 · p. 19
  • Under the conditional odd-characteristic hypotheses, dim(V110, V101, V011) ≥ 3 dim(V111).The proof uses complementary subspaces and shows that V110, V101, and V011 contain the corresponding pairwise projections of V111.Source: §6.2 · p. 20
  • A 27-dimensional vector Λodd yields an odd-characteristic inequality for every seven-subspace configuration, while the characteristic-2 Fano representation violates it.The inequality implies dim(V110, V101, V011) ≥ 3 dim(V111) in odd characteristic; for the Fano matroid, these dimensions instead satisfy dim(V110, V101, V011) = 2 dim(V111).Source: §6.2 · pp. 20, 22

6.3 Polynomial separation between the linear and non-linear rates

  • The Tightening Modification lemma constructs an explicit linear transformation that maps feasible dimension vectors to feasible vectors on a smaller index set while preserving specified all-ones and matroid-rank properties.It is implemented through quotienting by an added rank-zero element and successively projecting away indexed subspaces.Source: §6.3 · pp. 23–24
  • The Homomorphic Schema Extension lemma converts any universally valid linear constraint into a homomorphic constraint schema valid for every index set, and the schema is tight when the constraint annihilates the all-ones vectors.Rows are indexed by Boolean lattice homomorphisms, allowing the constraint to be transferred through compositions of index-set maps.Source: §6.3 · pp. 24–25
  • 16^n: The constructed product instance G^•n has non-linear broadcast rate β(G^•n) = 16^n.Submultiplicativity gives the upper bound, while supermultiplicativity of the trivial lower bound gives the matching lower bound.Source: §6.3 · p. 26
  • Although each factor has a linear solution over its appropriate field, the index code for G = G_F • G_N is highly nonlinear rather than a side-by-side combination of linear codes.The proof concatenates the factor codes through an arbitrary bijection between a mod-2 vector space and a mod-p vector space for odd p.Source: §6.3 · p. 26
  • (16+ε)^n: For every field F, the LP construction proves the linear broadcast rate satisfies λ_F(G^•n) ≥ (16+ε)^n.The proof treats characteristic 2 and non-2 fields separately, using different but nearly identical tight homomorphic constraint schemas derived from matroid rank inequalities.Source: §6.3 · p. 26
  • The LP lower bound applies because every linear index code induces entropy-derived rank vectors satisfying the constructed constraint system, establishing b_F(G) ≤ λ_F(G).The constraint schema combines a schema obtained from the matroid-based vector with submodularity, and its disjoint union remains tight and homomorphic.Source: §6.3 · pp. 25, 27
  • The strict base-case bound b_F(G) > 16 follows from a constraint row evaluating negatively on the relevant matroid rank function, using Theorem 6.4 or 6.6 according to field characteristic.Because the schema includes submodularity and each factor has b(G_F) = b(G_N) = 4, strictness for one factor yields the claimed product lower bound by supermultiplicativity.Source: §6.3 · p. 27
Loading 1108.2489v1…