Unweighted Code Sparsifiers and Thin Subgraphs

Given a code $\mathcal{C}$ over $\mathbb{F}_{2}^{n}$, its distance is defined as

$$\operatorname{dist}(\mathcal{C})\coloneq\min_{c\in\mathcal{C},c\neq 0}\operatorname{wt}(c),$$

where $\operatorname{wt}(c)=\|c\|_{0}$ is the number of nonzero coordinates of $c$. We say $\mathcal{C}$ is a linear code if for any $c,c^{\prime}\in\mathcal{C}$, $c+c^{\prime}\in\mathcal{C}$. We say $\mathcal{C}$ is $k$-dimensional if it has $2^{k}$ codewords. For convenience, we identify the set $S\subseteq[n]$ with its indicator vector $S\in\mathbb{F}_{2}^{n}$ (thus $2^{[n]}$ is identified with $\mathbb{F}_{2}^{n}$).

The projection of $\mathcal{C}$ onto $S\subseteq[n]$ is the code $\mathcal{C}_{S}=\{c_{S}:c\in\mathcal{C}\}$ obtained by taking the $S$ coordinates of every codeword in $\mathcal{C}$. Recently, Khanna-Putterman-Sudan [KPS24] initiated the study of code sparsification where they proved that any linear code $\mathcal{C}$ of dimension $k$ over $\mathbb{F}_{2}^{n}$ has a “weighted” code sparsifier which projects $\mathcal{C}$ onto at most $\widetilde{O}(k/\epsilon^{2})$-coordinates and such that the weighted hamming weight of every code word is preserved (up to a $1\pm\epsilon$ multiplicative error).

In our main theorem, we show that every linear code $\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$ has unweighted sparsifier $\mathcal{C}_{S}$ such that $\lvert S\rvert\approx n/2$ and $\operatorname{dist}(\mathcal{C}_{S})\geq\frac{1}{2}\operatorname{dist}(\mathcal{C})$. In other words, (assuming $k\ll n)$, we can increase the rate of the code by a factor of 2 while preserving almost the same distance-rate). Our main theorem is the following.

We remark that the proof of the theorem is not algorithmic. We also briefly explain applications of this theorem to thin subgraphs.
Given an unweighted (undirected) graph $G=(V,E)$ with $n$ vertices and $m$ edges, we say a set $T\subseteq E$ is a $\alpha$-thin w.r.t. $G$ if for any nonempty set $S\subsetneq V$,

$$\lvert T(S,\overline{S})\rvert\leq\alpha\lvert E(S,\overline{S})\rvert,$$

i.e., $T$ has at most $\alpha$-fraction of the edges of every cut. Recall that a graph $G$ is $t$-edge-connected if every cut in $G$ has at least $t$ edges. The following thin tree conjecture is proposed by Goddyn two decades ago [God04] and has been a subject of intense study since then [Asa+10, OS11, HO14, AO15, MP19, Mou, Alg23, KO23].

We remark that there has been several ”spectral” constructions of thin subsets but it remained an open problem whether one can construct thin subsets combinatorially without appealing to eigenvalue arguments (this is specially motivated to address the thin tree conjecture, since $t$-edge-connected graphs do not necessarily have spectrally thin trees, see [AO15]).

The following stronger statement also follows from our proof.

The bound is tight, as a spanning tree only has a single $1/2$-thin subgraph, the empty-set.
We remark that although the existence of $1/2$-thin subgraphs follows by spectral arguments such as [BSS14], we are not aware of any exponential lower-bound on the number of spectrally thin subgraphs.

Note that the collection of equivalence classes is the quotient space $\mathbb{F}_{2}^{n}/\mathcal{C}$ (this is a vector space over $\mathbb{F}_{2}$). Since $\dim\mathbb{F}_{2}^{n}/\mathcal{C}=n-k$ there are precisely $\lvert\mathbb{F}_{2}^{n}/\mathcal{C}\rvert=2^{n-k}$ equivalence classes.

For an equivalence class $H$, let $S_{H}\subseteq[n]$ be a set of the largest size in $H$. Lemma 2.2 implies that the collection $\left\{S_{H}\colon H\in\mathbb{F}_{2}^{n}/\mathcal{C}\right\}$ contains $2^{n-k}$ distinct subsets $S\subseteq[n]$ s.t. $\operatorname{dist}(\mathcal{C}_{S})\geq\frac{1}{2}\operatorname{dist}(\mathcal{C})$.

Now, it follows by the pigeon-hole principle that there must be a set $S\approx n/2$ such that $\mathcal{C}_{S}$ has distance at least half of the distance of $\mathcal{C}$.