A Unified Theory of Sparsification

We study the sparsifiability of \emph{real-valued codes}, a unifying abstraction that generalizes both combinatorial and continuous notions of sparsification, including spectral sparsification. In our setting, a code $C\subseteq {\mathbb{R}}_{\ge 0}^m$ is simply a collection of nonnegative real-valued vectors, and for a parameter $\epsilon >0$, a \emph{$(1\pm \epsilon )$-sparsifier} of $C$ is a subset $T\subseteq [m]$, together with weights $w\in {\mathbb{R}}_{\ge 0}^T$, such that, for every $c\in C$, ${\sum }_{i\in T}{w}_i{c}_i\in (1\pm \epsilon ){\sum }_{i=1}^m{c}_i$. When $C\subseteq \{0,1{\}}^m$, this specializes to code sparsification, and hence captures CSP sparsification, as studied by Khanna–Putterman–Sudan (SODA 2024, STOC 2025) and Brakensiek–Guruswami (STOC 2025). Similarly, for a graph $G=(V,E)$, if one defines $C=\{c^{(x)}:x\in {\mathbb{R}}^V\}\subseteq {\mathbb{R}}_{\ge 0}^E$ by $c_{(u,v)}^{(x)}=(x_u-x_v{)}^2$, then sparsifying $C$ is exactly spectral graph sparsification, as studied by Spielman–Teng (SICOMP 2011). Although the techniques driving combinatorial and continuous sparsification have traditionally been largely disjoint, our main result is a single structural theorem governing the sparsifiability of arbitrary real-valued codes $C\subseteq {\mathbb{R}}_{\ge 0}^m$. The central parameter is \emph{continuous-valued non-redundancy} ($\mathrm{C}\mathrm{V}\mathrm{N}\mathrm{R}\mathrm{D}$), a real-valued analogue of non-redundancy that captures the largest approximately block-diagonal obstruction contained in $C$. Our theorem gives sparsifiers of size nearly-linear in $\mathrm{C}\mathrm{V}\mathrm{N}\mathrm{R}\mathrm{D}$, and shows that $\mathrm{C}\mathrm{V}\mathrm{N}\mathrm{R}\mathrm{D}$ is also a lower-bound obstruction for the broad class of coordinate-wise unbiased randomized sparsification schemes.