A Unified Theory of Sparsification
2026-07-17 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to simplify complex collections of nonnegative real-valued vectors, called codes, without losing much information—a process called sparsification. They develop a unified theory that connects previous work on both discrete (combinatorial) and continuous sparsification methods, including graph spectral sparsification. Their main contribution is a structural theorem using a new concept called continuous-valued non-redundancy (CVNRD), which measures the complexity of these codes and dictates how small a sparsifier can be. They show that any sparsifier must roughly have size related to CVNRD, establishing both upper and lower bounds for a broad class of techniques.
SparsificationReal-valued codesSpectral graph sparsificationCombinatorial sparsificationContinuous sparsificationNon-redundancyContinuous-valued non-redundancy (CVNRD)Approximate block-diagonal structureCoordinate-wise unbiased randomized sparsificationConstraint Satisfaction Problems (CSP) sparsification
Authors
Sanjeev Khanna, Aaron Putterman, Madhu Sudan
Abstract
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}_{\geq 0}^m$ is simply a collection of nonnegative real-valued vectors, and for a parameter $ε> 0$, a \emph{$(1 \pm ε)$-sparsifier} of $C$ is a subset $T \subseteq [m]$, together with weights $w \in \mathbb{R}_{\geq 0}^T$, such that, for every $c \in C$, $\sum_{i \in T} w_i c_i \in (1 \pm ε)\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_{\geq 0}^E$ by $c^{(x)}_{(u,v)}=(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}_{\geq 0}^m$. The central parameter is \emph{continuous-valued non-redundancy} ($\mathrm{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 $\mathrm{CVNRD}$, and shows that $\mathrm{CVNRD}$ is also a lower-bound obstruction for the broad class of coordinate-wise unbiased randomized sparsification schemes.