2026/07/17 by Sanjeev Khanna, Aaron Putterman, Madhu Sudan
#cs.DS
We study the sparsifiability of real-valued codes, a unifying abstraction that generalizes both combinatorial and continuous notions of sparsification, including spectral sparsification. In our setting, a code C ⊆ ℝ≥ 0m is simply a collection of nonnegative real-valued vectors, and for a parameter ε> 0, a (1 ± ε)-sparsifier of C is a subset T ⊆ [m], together with weights w ∈ ℝ≥ 0T, such that, for every c ∈ C, ∑i ∈ T wi ci ∈ (1 ± ε)∑i=1m ci. When C ⊆ \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∈\mathbb RV\⊆\mathbb R≥ 0E by c(x)(u,v)=(xu-xv)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⊆ℝ≥ 0m. The central parameter is continuous-valued non-redundancy (CVNRD), 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 CVNRD, and shows that CVNRD is also a lower-bound obstruction for the broad class of coordinate-wise unbiased randomized sparsification schemes.