Let C⊆F_2^n be a linear code. A hitting set for C is a set S⊆[n] such that c_S≠0 for every nonzero codeword c∈C. Suppose that C has at least d disjoint hitting sets S_1,…,S_d. Thin code conjecture. For any alpha<1, there exists an integer d=d(alpha)≥1 such that there is a set S⊆[n] satisfying, for every nonzero c∈C, alpha·operatornamewt(c)≤operatornamewt(c_S)<operatornamewt(c). This conjecture generalizes the thin tree conjecture to binary linear codes by seeking a single set that captures an alpha-fraction, but not all, of the support of every nonzero codeword. The supplied text does not establish whether it is open or resolved.

Thin code conjecture for binary linear codes

Let $\mathcal{C}\subseteq\mathbb{F}_2^n$ be a linear code. A hitting set for $\mathcal{C}$ is a set $S\subseteq[n]$ such that $c_S\neq0$ for every nonzero codeword $c\in\mathcal{C}$ . Suppose that $\mathcal{C}$ has at least $d$ disjoint hitting sets $S_1,\dots,S_d$ . Thin code conjecture. For any $\alpha<1$ , there exists an integer $d=d(\alpha)\geq1$ such that there is a set $S\subseteq[n]$ satisfying, for every nonzero $c\in\mathcal{C}$ ,

\alpha\cdot\operatorname{wt}(c)\leq\operatorname{wt}(c_S)<\operatorname{wt}(c).

This conjecture generalizes the thin tree conjecture to binary linear codes by seeking a single set that captures an $\alpha$ -fraction, but not all, of the support of every nonzero codeword. The supplied text does not establish whether it is open or resolved.

The conjecture asks whether sufficiently many disjoint hitting sets force one set to capture a fixed fraction, but not all, of every nonzero codeword. It generalizes Goddyn’s thin tree conjecture, proposed about two decades earlier.

Known results

Every $k$ -dimensional code has at least $2^{n-k}$ unweighted one-sided $1/2$ -sparsifiers.
One such sparsifier has size at most $n/2+O(\sqrt{nk})$ .
These results do not ensure $\operatorname{wt}(c_S)<\operatorname{wt}(c)$ for every nonzero codeword, nor do they derive the conjecture from disjoint hitting sets.

February–October 2025 developments

The February manuscript states the thin code conjecture explicitly and leaves it open; it also notes that a stronger earlier formulation was refuted by Putterman for random linear codes. An October 2025 follow-up proves computational hardness for finding minimum-size one-sided $1/2$ -sparsifiers, but gives no proof or counterexample to the conjecture.

Current status (as of August 2026): The thin code conjecture remains open, with related existence and hardness results but no verified proof or counterexample recorded.

Thin code conjecture for binary linear codes

Primary source

Progress summary

Solutions 0