Source-linked AI summary
A Matroidal Framework for Random Access in Linear Codes
Daniella Bar-Lev, Hiram H. López, Gretchen L. Matthews, Flavio Salizzoni
TL;DR
In uniform random-access sampling for linear codes, the paper asks how expected recovery times across coordinates relate to matroid structure and code duality. It expresses recovery expectations through the associated matroid and derives a coordinatewise duality identity. This proves that a code is recovery balanced exactly when its dual is, while asymptotically almost every sparse paving matroid is not recovery balanced.
Problem
In uniform random access for linear codes, the paper studies coordinate recovery expectations and whether recovery balance is preserved under code duality, a conjecture of Gruica et al.
Source: §I · p. 1Method
The paper expresses coordinate recovery expectations as matroid invariants and derives a coordinatewise identity relating a code to its dual.
Source: §III · p. 3, §IV · p. 4Results
A linear code is recovery balanced if and only if its dual is, and asymptotically almost every sparse paving matroid is not recovery balanced.
Source: §IV · p. 4, §V · p. 5Takeaways & Limitations
Recovery balance is a matroidal property for codes, and the sparse paving result shows it is uncommon among sparse paving matroids as their size grows.
Source: §I · p. 1, §V · pp. 4–5
Abstract
from arXiv · showhide
We study random access in linear codes when codeword symbols are sampled independently and uniformly with replacement. A code is recovery balanced if the expected number of samples required to recover a codeword coordinate is the same for every coordinate. We express the recovery expectations in terms of the associated matroid and derive a coordinatewise identity relating these values for a code and its dual. This proves that a linear code is recovery balanced if and only if its dual is recovery balanced, establishing a conjecture of Gruica et al. We further define the recovery balance for arbitrary matroids and show that asymptotically almost every sparse paving matroid is not recovery balanced.
I. INTRODUCTION
The paper studies single-symbol random access in the uniform noiseless sampling model, where recovery depends on linear dependencies among generator-matrix columns. It makes recovery balance matroidal, proves balance is preserved under code duality, and shows that asymptotically almost every sparse paving matroid is not recovery balanced.
I. INTRODUCTION
- The coded coupon collector problem models recovery from independently and uniformly sampled encoded symbols, with the objective of minimizing expected samples to recover requested information.The problem was introduced with motivation from DNA-based data storage.Source: §I · p. 1
- Prior work studies full recovery, requested collections of files or symbols, file-retrieval tradeoffs, and partial reconstruction.The paper situates its single-symbol random-access setting among these distinct recovery objectives.Source: §I · p. 1
- In the uniform noiseless model, random access requests one information symbol, recoverable when it is a linear combination of sampled symbols.Thus, expected recovery time depends on dependencies among generator-matrix columns.Source: §I · p. 1
- Recovery balance means equal expected recovery times across all codeword coordinates; each coordinate then has expectation k, so systematic information symbols match uncoded recovery time.Improving on that baseline requires a code that is not recovery balanced.Source: §I · p. 1
- A linear code is recovery balanced if and only if its dual is, proving the conjecture over every finite field.The paper identifies recovery balance as a matroidal property and extends the preservation result to matroids without loops or coloops.Source: §I · p. 1
- For every rank 1 ≤ k ≤ n − 1, the proportion of recovery-balanced sparse paving matroids on n elements is at most 4/n for sufficiently large n.Consequently, asymptotically almost every sparse paving matroid is not recovery balanced.Source: §I · pp. 1–2
II. NOTATION AND DEFINITIONS
The paper fixes notation for finite fields, the ground set of n elements, harmonic numbers, and linear span.
II. NOTATION AND DEFINITIONS
- Throughout, q is a prime power, Fq is the finite field with q elements, [n] = {1, . . . , n}, and Hn is the n-th harmonic number with H0 = 0.The notation ⟨·⟩ denotes span over Fq.Source: §II · p. 2
A. Linear Codes and Recovery Balance
The section formalizes random-access recovery for linear codes and recalls recovery balance and its duality conjecture. It relates recovery time to whether the requested generator column lies in the span of sampled columns.
A. Linear Codes and Recovery Balance
- For coordinate i, recovery time is the number of independent uniform draws with replacement from [n] until generator column gi lies in the span of the drawn columns; it is zero when gi = 0.Its expectation depends only on the code, not on the chosen generator matrix.Source: A. Linear Codes and Recovery Balance · p. 2
- A code is recovery balanced when the expected recovery times of all n codeword coordinates are equal.For an [n, k]q code, the average coordinate expectation is k, so every coordinate expectation is k when the code is recovery balanced.Source: A. Linear Codes and Recovery Balance · p. 2
- The section states the conjecture that a code is recovery balanced if and only if its dual is recovery balanced; the paper proves it for every linear [n, k]q code.The conjecture had previously been proved for codes with a transitive permutation automorphism group.Source: A. Linear Codes and Recovery Balance · p. 2
- The recovery-time counting function is determined by the linear dependencies among generator-matrix columns, and the argument for a requested column applies when gi is nonzero.When gi is nonzero, eαi(0) = 0; the dependencies are then expressed using matroids.Source: A. Linear Codes and Recovery Balance · p. 2
B. Matroids and Duality
The section introduces matroids through rank, independence, closure, and duality, then connects those concepts to generator-matrix dependencies and code duals. A rank-increment relation links closure in a matroid to closure in its dual.
B. Matroids and Duality
- A matroid is defined by a rank function satisfying bounds, monotonicity, and submodularity; a set is independent when its rank equals its size, and a minimal dependent set is a circuit.Closure comprises elements whose addition leaves rank unchanged.Source: B. Matroids and Duality · p. 2
- The code matroid is representable over Fq, and its dual is the matroid of the dual code; generator and parity-check matrices yield dual matroids.The dual of a matroid is itself a matroid, and taking the dual twice returns the original.Source: B. Matroids and Duality · pp. 2–3
- In a code matroid, adjoining index i to a set leaves its rank unchanged exactly when column gi lies in the span of the corresponding columns, so recovery counting can be expressed through matroid closure.The matroid of a code is independent of the generator matrix chosen, because invertible row operations preserve column dependencies.Source: B. Matroids and Duality · p. 2
- In the code matroid, i is a loop exactly when gi = 0 and a coloop exactly when gi is outside the span of all other generator columns.These cases identify the extreme recovery situations treated by the section.Source: B. Matroids and Duality · p. 2
- For S excluding i and T = [n] \ (S ∪ {i}), i lies in the closure of S exactly when it does not lie in the dual closure of T.Equivalently, the rank increment from adding i is zero in the first case and one in the other, with the dual increment reversed.Source: B. Matroids and Duality · p. 3
III. THE EXPECTATION AS A MATROID INVARIANT
Coordinate recovery expectations depend only on matroidal counting data, and recovery balance extends beyond representable matroids. A coordinatewise dual counting identity supplies the tool for the duality result.
III. THE EXPECTATION AS A MATROID INVARIANT
- The counting function, and hence each coordinate's expected recovery time, depends only on the code's associated matroid.The section derives the expectation using the number of sampled subsets whose closure contains the requested coordinate.Source: §III · p. 3
- The coordinate count separates subsets containing i from those not containing i, with the latter counted by a_i^M(s).This subset split is used to derive the expectation expression.Source: §III · p. 3
- A zero generator column has expected recovery time n, whereas an MDS code has expected recovery time k.These are the two extreme cases described in the section.Source: §III · p. 3
- Recovery balance extends to arbitrary matroids, and a code is recovery balanced exactly when its associated matroid is.The extension does not require representability.Source: §III · p. 3
- Complementing subsets of [n]\{i} converts closure counts in M into non-closure counts in M*, giving the coordinatewise identity used for duality.The proof pairs each s-subset with its complement among the coordinates other than i.Source: §III · p. 3
IV. THE DUALITY IDENTITY AND PROOF OF CONJECTURE 1
The section gives a coordinatewise duality identity for recovery expectations and uses it to prove that a linear code is recovery balanced exactly when its dual is.
IV. THE DUALITY IDENTITY AND PROOF OF CONJECTURE 1
- A linear code is recovery balanced if and only if its dual is recovery balanced.The proof handles the zero- and full-dimension cases directly, then applies the identity in the nontrivial case.Source: §IV · p. 4
- For 0 < k < n, a balanced code’s matroid has no loops or coloops, and the identity gives its dual the common recovery value n − k.The proof treats k = 0 and k = n separately; in the interior case, the common value k is independent of coordinate i.Source: §IV · p. 4
- The dual’s entire coordinate recovery profile is the reflection E[eτ_i] → n − E[eτ_i], even without balance, when both codes are non-degenerate.This coordinatewise statement is stronger than the balance-preservation conjecture.Source: §IV · p. 4
V. SPARSE PAVING MATROIDS
For sufficiently large n, at most 4/n of rank-k sparse paving matroids are recovery balanced, so asymptotically almost every sparse paving matroid is not. The section relates this property to regular independent sets of Johnson graphs and notes that the result does not quantify representable matroids.
V. SPARSE PAVING MATROIDS
- Sparse paving matroids of rank k correspond bijectively to independent sets of J(n, k), whose vertices are the k-subsets of [n].Two vertices are adjacent when their subsets intersect in k − 1 elements.Source: §V · p. 4
- A sparse paving matroid of rank k is recovery balanced exactly when its dependent k-sets have equal incidence counts across all n elements.In that case, n divides km and every incidence count equals km/n.Source: §V · p. 5
- Counting recovery balanced sparse paving matroids reduces to counting regular independent sets in the Johnson graph J(n, k).The proof estimates regular independent sets separately by small and large cardinalities.Source: §V · p. 5
- The authors believe the sparse paving assumption may be removable, which would extend the conclusion to almost every matroid.They describe this broader conclusion as a belief, not as the theorem proved here.Source: §V · p. 5
- The result concerns the uniform measure on sparse paving matroids and implies nothing about the proportion of representable ones.The authors note that representable matroids have asymptotically zero measure among all matroids, leaving the size of representable sparse paving matroids unaddressed.Source: §V · pp. 5–6
AI DISCLOSURE
The paper acknowledges Claude Fable's suggestions and reports using ChatGPT-6 Astra for grammar and wording.
AI DISCLOSURE
- Claude Fable suggested a proof strategy for Theorem 4 and a matroid-theoretic connection developed by the authors; ChatGPT-6 Astra assisted with grammar and wording.Source: AI DISCLOSURE · p. 6