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.

Sources & referencesView supporting material

Primary source

Shayan Oveis Gharan and Arvin Sahami, “Unweighted One-Sided Code Sparsifiers and Thin Subgraphs”, arXiv:2502.02799 (2025).

1 week ago

Progress summary

Refreshed 4 days ago

Partially solved

The conjecture remains unproved, but a 2025 paper established related sparsifier results and a later paper studied their computational difficulty.

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.

Sources

arxiv.org

No solutions have been posted yet.