Technical Summary: Cofilling Shattering: A Syndrome-Support Hierarchy for Check Erasures

1. Problem Statement

The paper addresses a fundamental gap in the analysis of binary linear codes and their parity-check matrices. While standard coding theory treats the kernel code $C_A = \ker A$ as the primary object, the specific realization of the parity-check matrix $A: \mathbb{F}_2^n \to \mathbb{F}_2^m$ (i.e., the specific set of check generators) carries operational information often ignored by row-equivalence.

The central problem is to quantify the vulnerability of a specific check realization to the erasure of check coordinates. Specifically, the authors ask: How many check coordinates must be erased to release a syndrome subspace where every nonzero syndrome requires a high-weight error (low-weight preimage) to realize?

This distinguishes between:

1. Rank-only vulnerability: Releasing any $q$-dimensional syndrome subspace (controlled by generalized Hamming weights).
2. Localization-sensitive vulnerability: Releasing a subspace where every nonzero element has a coset-leader weight (minimum preimage weight) of at least $s$.

The paper argues that two parity-check matrices defining the same code can have identical generalized covering radii and generalized Hamming weights but exhibit drastically different vulnerabilities to check erasure due to the specific linear combinations of checks they represent.

2. Methodology and Definitions

2.1 The Cofilling Shattering Hierarchy

The authors define a new invariant, Shat$_{q,s}(A)$, for a binary linear map $A$ with fixed coordinate bases:
$$\text{Shat}_{q,s}(A) = \min \{ |\text{supp } U| : U \leq \text{im } A, \dim U = q, \lambda_A(y) \geq s \text{ for all } 0 \neq y \in U \}$$
where:

• $\lambda_A(y) = \min \{ |x| : Ax = y \}$ is the coset-leader weight (minimum variable weight) for syndrome $y$.
• $\text{supp } U$ is the union of supports of all vectors in the subspace $U$.
• $q$ is the dimension of the released syndrome subspace.
• $s$ is the minimum required localization (difficulty) for every nonzero syndrome in that subspace.

This quantity represents the minimum number of check coordinates that must be erased to "shatter" the system, releasing a $q$-dimensional space of "hard" syndromes.

2.2 Topological Specialization

The framework is specialized to simplicial coboundary maps $A = \delta_k$ of a simplicial complex $X$.

• Check Erasure: Deleting a set of top faces $F \subseteq X(k+1)$ corresponds to deleting rows of $\delta_k$.
• Emergent Cohomology: The quotient space $H_k(X-F) / H_k(X)$ is canonically isomorphic to the shortened top coboundary code $C_{X}^{k+1}[F]$.
• Interpretation: The hierarchy measures the minimum number of top faces to delete to create a $q$-dimensional space of new cohomology classes, where every new class has a representative (filling) of size at least $s$.

2.3 Graph Interpretation

For $k=0$ (graphs), the problem maps to finding a labeling of vertices such that the set of edges where labels differ (the cut) is minimized, subject to constraints on the affine span of labels and the size of label fibers (balanced multiway cuts).

3. Key Contributions and Results

3.1 The Check-Basis Dependence (Result R3)

A primary contribution is the proof that $\text{Shat}_{q,s}(A)$ is not invariant under row operations (change of check basis), even if the kernel code, rank, and image code remain identical.

• Example: For the pair-repetition code $C_n = \{(x,x)\}$, the standard realization $H_0 = [I_n \mid I_n]$ yields $\text{Shat}_{q,s}(H_0) = N_2(q, s)$ (the shortest length of a binary code with dimension $q$ and distance $s$).
• However, there exists a row-equivalent matrix $H_1$ for the same code where $\text{Shat}_{q,s}(H_1) = q$.
• This demonstrates that the "collective separation" of checks matters: a specific basis can hide a difficult syndrome subspace behind a small set of checks, whereas another basis requires a much larger set.

3.2 Bounds and Obstructions (Results R2, R4)

The paper establishes several lower bounds for $\text{Shat}_{q,s}(A)$:

• Code Length Bound: If $\text{Shat}_{q,s}(A) < \infty$, then the rank of $A$ must satisfy $r \geq N_2(q, s)$, where $N_2(q, s)$ is the Griesmer bound for binary codes.
• Profile-Griesmer Bound: $\text{Shat}_{q,s}(A) \geq \max \{ d_q(\text{im } A), G_q(\Sigma_A(s)) \}$, where $d_q$ is the $q$-th generalized Hamming weight and $\Sigma_A(s)$ is the monotone envelope of the minimum support for syndromes with localization $s$.
• Topological Bounds: For simplicial complexes, the hierarchy is bounded by the expansion constant $h_k(X)$ and the geometry of the complex.

3.3 Random Erasures and Matroid Structure

The authors analyze independent random erasures of check coordinates:

• Rank Increments: The expected dimension of the emergent quotient depends only on the matroid of the check matrix (Tutte polynomial specialization).
• Localization Sensitivity: The probability of releasing a "hard" syndrome subspace depends on the bivariate shattering enumerator $W_X(a, b)$, which tracks both the support size and the minimum preimage weight of codewords.
• Tail Bounds: The paper derives exponential tail bounds for the probability of creating large, localized defects in high-dimensional expanders.

3.4 Sharpness and Extremal Cases

• Simplex Boundaries: For the boundary of a simplex, the paper provides exact formulas for $\text{Shat}_{q,s}$, showing that the profile-Griesmer bound is attained for infinite families of parameters.
• Graph Cuts: The graph case is formulated as a "Fourier-balanced multiway cut," linking the shattering parameter to the spectral gap (Fiedler eigenvalue) and Ky Fan principles.

4. Significance and Claims

The paper claims to introduce a syndrome-support hierarchy that couples two previously distinct concepts:

1. Generalized Hamming Weights: Which control the support of subcodes.
2. Generalized Covering Radii: Which control the generation of syndromes.

Key Distinctions from Existing Frameworks:

• Unlike Generalized Hamming Weights, which are invariants of the code itself, $\text{Shat}_{q,s}$ is an invariant of the check realization. It captures the operational vulnerability of specific check generators.
• Unlike Stopping Sets, which concern variable erasures in iterative decoding, this work concerns check erasures and constrains the entire syndrome subspace, not just a basis.
• Unlike Generalized Covering Radii, which measure the columns needed to span syndromes, this work measures the common support of a subspace where every element is "hard" (high coset-leader weight).

Motivation and Application:
The framework is motivated by the study of high-dimensional expanders and topological codes (specifically CSS codes). In these contexts, erasing checks (faces) releases logical operators (cohomology classes). The paper argues that understanding the localization of these released classes (how "spread out" their fillings are) is crucial for assessing the resilience of the code against specific types of check failures.

The authors explicitly state that the term "cofilling" refers to the minimum-preimage coordinate, and "shattering" refers to the loss of a common set of check generators, unrelated to VC dimension. The work provides exact dictionaries between check erasure and shortened codes, and establishes that for $s \geq 2$, even identical labeled cut codes can have different values, highlighting the necessity of analyzing the specific check basis rather than just the code equivalence class.