Multiplicative Error Set System Sparsification: A Simpler Proof via Chain Length Contraction

Brakensiek, Joshua; Guruswami, Venkatesan; Putterman, Aaron

doi:10.4230/LIPIcs.ICALP.2026.44

Multiplicative Error Set System Sparsification:
A Simpler Proof via Chain Length Contraction

Joshua Brakensiek

Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA, USA Venkatesan Guruswami

Simons Institute for the Theory of Computing and the University of California, Berkeley, CA, USA Aaron Putterman

School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA

Abstract

The chain length of a set family $\mathcal{S}\subseteq 2^{[m]}$ is the largest ascending sequence of sets in containment order in the union-closure of $\mathcal{S}$ . In this work, we provide a significantly simpler and more optimal characterization of the sparsifiability of set systems in terms of their chain length, improving on the work of Brakensiek and Guruswami [STOC 2025]. Our proof relies on a generalization of Karger’s [SODA 1993] famous contraction algorithm and its recent linear algebraic extensions [Khanna-Putterman-Sudan SODA 2024], and our resulting bounds show that, just as VC dimension characterizes the additive sparsifiability of a set system, chain length governs the multiplicative sparsifiability. As a corollary, we obtain improved bounds for weighted CSP sparsification.

Keywords and phrases:

constraint satisfaction problem, chain length, sparsification, VC dimension

Category:

Track A: Algorithms, Complexity and Games

Funding:

Joshua Brakensiek: Supported in part by the Simons Investigator award of Venkatesan Guruswami and NSF grants CCF-2211972 and DMS-2503280.

Venkatesan Guruswami: Supported in part by a Simons Investigator award and NSF award CCF-2211972.

Aaron Putterman: Supported in part by the Simons Investigator Awards of Madhu Sudan and Salil Vadhan and AFOSR award FA9550-25-1-0112.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Constraint and logic programming

Acknowledgements:

We thank anonymous reviewers for many helpful comments improving the presentation of this paper. We also thank an anonymous reviewer of [7] whose comments partially inspired Theorem 22. A. P. thanks Sanjeev Khanna and Madhu Sudan for helpful conversations.

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In theoretical computer science, sparsification describes a range of methods for reducing the storage size of a mathematical object while preserve some of its essential qualities. In this paper, we study the sparsification of set systems $\mathcal{S}\subseteq 2^{[m]}$ where $[m]:=\{1,2,\ldots,m\}$ is a finite set of atoms. Here, we define sparsification analogously to that of Karger’s definition for graph cuts [19], where we find a reweighting $w:[m]\to\mathbb{R}_{\geq 0}$ of the atoms such that for every set $S\in\mathcal{S}$ , its weight before and after the reweighting match up to a multiplicative error of $1\pm\epsilon$ (see Section 2 for a formal definition). In general, the goal is to find a map $w$ such that the support $\operatorname{supp}(w):=\{i\in[m]:w(i)\neq 0\}$ is as small as possible.

This framework precisely recover the graph cut sparsification framework of Karger, if we let $[m]$ represent the set of edges of an undirected graph $G=(V,E)$ , and let $\mathcal{S}$ be the family of all possible cuts of $G$ (i.e., sets of the form $(A\times(V\setminus A))\cap E$ , where $A\subseteq V$ . In this paper, we prove general bounds on the sparsifiability of all set systems, even when the initial atoms $[m]$ are also weighted.

The general study of set system sparsifiers was initiated by Brakensiek and Guruswami [7] to help resolve questions in the emerging area of CSP sparsification, see Section 1.2 for further background. In particular, they showed that the optimal size of a (weighted) set system sparsifier is closely related to the chain length (coined by Bessiere, Carbonnel, and Katsirelos [5]) of the set system. For a set system $\mathcal{S}\subseteq 2^{[m]}$ , we define its chain length $\mathrm{CL}(\mathcal{S})$ to be the length of the longest ascending chain of sets $S_{1}\subsetneq\cdots\subsetneq S_{\mathrm{CL}(\mathcal{S})}$ contained in $\bigcup\mathcal{S}$ , the closure of $S$ with respect to set union–see Section 2 for a formal definition. We now state the main result of Brakensiek and Guruswami [7] on weighted set system sparsification.

Theorem 1 (Theorem 1.4 of [7]).

For a set system $\mathcal{S}\subseteq 2^{[m]}$ , weights $w:[m]\rightarrow\mathbb{R}_{\geq 0}$ and $\epsilon>0$ , there exists a $(1\pm\epsilon)$ sparsifier of $\mathcal{S}$ which retains only

O\left(\frac{\mathrm{CL}(\mathcal{S})\log^{6}m}{\epsilon^{2}}\right)

many atoms.

Of note, this bound is “near-optimal” in the sense that for any set system $\mathcal{S}\subseteq 2^{[m]}$ , there is a set of weights $w$ such that any sparsifier needs at least $\mathrm{CL}(\mathcal{S})$ atoms (see Lemma 8.9 of [7]¹¹1Lemma 8.9 appears in the full version of their paper at https://arxiv.org/abs/2411.03451.). Furthermore, by a data structure lower bound of Carlson, Kolla, Srivastava and Trevisan [9] for graph cuts, we know that the dependence on $\epsilon>0$ is optimal in the worst case. The main inefficiency in the bound of Theorem 1 is thus the additional factor of $\log^{6}(m)$ .

The proof of Theorem 1 is rather complex, as the proof first seeks to find near-optimal sparsifiers in the unweighted setting by adapting techniques pioneered by Gilmer [14] in his recent breakthrough on the union-closed set conjecture (see [7] for a much more detailed history of this problem).

1.1 Main Result

Our main result is a much more direct proof of Theorem 1 using a “contraction”-style argument similar to those used in many papers in the sparsification literature [19, 4, 12, 24, 13, 23]. As a consequence, we also get a much sharper asymptotic analysis.

Theorem 2 (Main Result, see Theorem 22).

For a set system $\mathcal{S}\subseteq 2^{[m]}$ , weights $w:[m]\rightarrow\mathbb{R}_{\geq 0}$ and $\epsilon>0$ , there exists a $(1\pm\epsilon)$ sparsifier of $\mathcal{S}$ which retains only

O\left(\frac{\mathrm{CL}(\mathcal{S})\cdot\log^{2}(\mathrm{CL}(\mathcal{S})/% \epsilon)\cdot(\log\log(\mathrm{CL}(\mathcal{S})/\epsilon))^{2}}{\epsilon^{2}}\right)

many atoms.

Theorem 2 improves on Theorem 1 in two ways. First, the multiplicative overhead of $\log^{6}m$ is reduced to a much smaller $\log^{2+o(1)}(\mathrm{CL}(\mathcal{S})/\epsilon)$ . Second, the bound in Theorem 2 is independent²²2We observe that the bound in Theorem 1 could also be made independent of $m$ by applying a recursive argument similar to that of Section 4.2. Even so, the asymptotics of Theorem 2 would still be superior. of $m$ !

As an application of the above theorem, one can consider a graph $G=(V,E)$ , and the set system $\mathcal{S}\subseteq 2^{E}$ which contains all the cuts in the graph $G$ . I.e., for every set $T\subseteq V$ , one can consider the set of edges $E_{T}\subseteq E$ which is cut by the set $T$ and let $\mathcal{S}=\bigcup_{T\subseteq V}E_{T}$ . Sparsifying the set system $\mathcal{S}$ is thus equivalent to creating a cut-sparsifier of the graph $G$ in the classical sense of [4]. Because the chain length of the set of cuts is bounded by $|V|$ , Theorem 2 recovers (up to an extra $\widetilde{O}(\log(m))$ factor) the sparsifier size bound of [4].

Note that Theorem 2 is however not efficiently implementable. This is in large part due to the fact that, given a set system $\mathcal{S}\subseteq 2^{[m]}$ , there is no known efficient algorithm for computing $\mathrm{CL}(\mathcal{S})$ .

1.1.1 Improvement to Code Sparsification

As an additional corollary to Theorem 2, we give the first bound for linear code sparsification (see [23]) which is independent of the underlying finite field. In more detail, given a finite field $\mathbb{F}_{q}$ on $q$ elements, we define a linear code to be an $n$ -dimensional subspace $C\subseteq\mathbb{F}_{q}^{m}$ . A $(1\pm\epsilon)$ sparsifier of $C$ is a reweighting $w:[m]\to\mathbb{R}_{\geq 0}$ such that for every $c\in C$ we have that

\sum_{i=1}^{m}w(i)\mathbf{1}[c_{i}\neq 0]\in(1\pm\epsilon)\sum_{i=1}^{m}% \mathbf{1}[c_{i}\neq 0].

A main result of Khanna, Putterman, and Sudan [23] (see also [21]) is that $C$ has a $(1\pm\epsilon)$ sparsifier of size³³3Size here is meant to be to the number of non-zero weights that are assigned; equivalently, the number of coordinates in $[m]$ that are retained. $|\operatorname{supp}(w)|=n\log^{O(1)}(n)\log q/\epsilon^{2}$ . If we capture linear code sparsification by letting our set system $\mathcal{S}$ be $\{\operatorname{supp}c:c\in C\}$ , then we obtain a linear code sparsifier of size $\mathrm{CL}(\mathcal{S})\log^{2+o(1)}(\mathrm{CL}(\mathcal{S})/\epsilon)/% \epsilon^{2}$ . From existing results on chain length [5, 7], we know that $\mathrm{CL}(\mathcal{S})$ is precisely the dimension $n$ of the code $C$ . This gives the first field-size independent bound of $n\cdot\log^{2+o(1)}(n/\epsilon)/\epsilon^{2}$ for code sparsification!

Lastly, recall that both [7], Theorem 1 and [23] used Theorem 1 and linear code sparsification respectively to design CSP sparsifiers. Because of our better parameters in Theorem 2, we immediately obtain tighter bounds for these applications.

1.2 Related Work

We now briefly discuss how our work connects to other parts of the sparsification and broader TCS literature.

1.2.1 Code, CSP, and Cayley graph sparsification

As previously mentioned, Khanna, Putterman and Sudan [23] pioneered the concept of code sparsification. In their original paper, [23] presented multiple applications of code sparsification including constraint satisfaction problem (CSP) sparsification and Cayley graph sparsification.

CSP sparsification was introduced by Kogan and Krauthgamer [24] to generalize graph cut sparsification to broader families of discrete structures, including hypergraph cut sparsification (e.g., [28, 10, 18, 17, 25, 16, 20]). A more systematic investigation of general CSP sparsification was started by Filtser–Krauthgamer [11] and Butti–Živný [8]. However, the case of linear equations over a finite field was not resolved until the method of code sparsification was developed [23]. In a follow-up Khanna, Putterman and Sudan [21] extended these methods to equations over Abelian groups among other CSPs. However, results concerning all CSPs were not established until Brakensiek and Guruswami [7] generalized linear code sparsification to non-linear codes (i.e., arbitrary set systems).

In a separate direction, the work of Khanna, Putterman and Sudan [23] introduced Cayley graph sparsification as a special case of graph cut sparsification where the input graph is a Cayley graph (i.e., the graph is defined by the generators of a suitable group). Here, the goal is not to construct any sparsifier, but rather a sparsifier which is itself a Cayley graph. Khanna, Putterman and Sudan [23] handled the case in which the Cayley graph corresponds to spanning vectors of a finite vector space. More recently, such methods were generalized to arbitrary groups [15], and even a more general theory of sparsifying sums of PSD matrices [2].

1.2.2 Chain length and query complexity

The notion of chain length was introduced by Bessiere, Carbonnel, and Katsirelos [5] in the context of analyzing the query complexity of constraint satisfaction problems in a model introduced by Bessiere et al. [6]. In this query model, one is not given explicit access to the constraints; rather, one queries a partial assignment to a subset of the variables, and the response is “YES” or “NO” depending on whether the partial assignment is consistent with all constraints induced by those variables. To connect this problem with the concept of chain length, consider a set system $\mathcal{S}\subseteq 2^{[m]}$ where $[m]$ represents the clauses of the CSP and $S\in\mathcal{S}$ if and only if there is a valid assignment to the CSP which satisfies the clauses indexed by $S$ (and no others). Then, $\widetilde{O}(\mathrm{CL}(\mathcal{S}))$ is an upper bound on the query complexity of this problem. However, it is an open question whether this chain length bound is tight. See [7] for further discussion.

1.2.3 Connections to Learning Theory

Recall that chain length of $\mathcal{S}\subseteq 2^{[m]}$ is the length of the longest ascending chain in $\bigcup\mathcal{S}$ . Another natural property of a set family $\bigcup\mathcal{F}$ is its VC-dimension. That is, the size of the largest set $A\subseteq[m]$ such that for all $B\subseteq A$ , there is some $S\in\mathcal{F}$ with $S\cap A=B$ . Bessiere, Carbonnel, and Katsirelos [5] define the non-redundancy of $\mathcal{S}$ , denoted by $\operatorname{NRD}(\mathcal{S})$ to be precisely the VC-dimension of $\bigcup\mathcal{S}$ . Brakensiek and Guruswami [7] identify the non-redundancy of $\mathcal{S}$ is closely related to the sparsifiability of $\mathcal{S}$ , assuming $\mathcal{S}$ is unweighted.

More broadly, the VC-dimension of a set family $\mathcal{F}\subseteq 2^{[m]}$ is well-known to characterize the sample complexity needed to obtain a small additive-error approximation of the set-sizes in the family. That is, with constant probability a random subset $T\subset[m]$ of size $O(\text{VC-dim}(\mathcal{F})/\epsilon^{2})$ [29, 1] satisfies $|T\cap S|\in|S|\pm\epsilon m$ for every $S\in\mathcal{F}$ . Conversely, no set of size smaller than $\Omega_{\epsilon}(\text{VC-dim}(\mathcal{F}))$ can satisfy such a guarantee.

In this view, the chain length characterizes the sample complexity needed to obtain multiplicative-error approximation to set-sizes, in the weighted setting. Note that, unlike the VC-theorem which works with unweighted samples, reweighting of the chosen samples is necessary to obtain a multiplicative approximation. We also remark that an unweighted multiplicative sampling theorem (relative to VC-dimension) was proved by Li, Long, and Srinivasan [26]; however, their notion of multiplicative approximation significantly differs from ours.

Organization

In Section 2, we state some known results (Chernoff bounds, etc.). In Section 3, we prove a key counting bound by relating the technique of contractions to chain length. In Section 4, we use the results of Section 3 to construct a series of sparsifiers, culminating in Theorem 2. In Section 5, we give some concluding thoughts and open questions.

2 Preliminaries

We now present some background material on sparsification and related concepts.

2.1 Notation and Sparsification Definitions

For the purposes of our analysis, we represent set systems $\mathcal{S}\subseteq 2^{[m]}$ as a set of vectors (also called a code) $C\subseteq\{0,1\}^{m}$ , where $S\in\mathcal{S}$ if and only if $c\in C$ where $c\in\{0,1\}^{m}$ is defined by

c_{i}=\begin{cases}1&i\in S\\ 0&i\not\in S.\end{cases}

Optionally, the coordinates $[m]$ of the code may be given weights $w:[m]\rightarrow\mathbb{R}_{\geq 0}$ . Note that when no weights are provided for the code, we assume that the weights are all $1$ (equivalently, an unweighted code). Occasionally, for a code $C\subseteq\{0,1\}^{m}$ and a set $S\subseteq[m]$ , we will use the notation $C|_{S}=\{c|_{S}:c\in C\}$ to be the coordinate restriction of all codewords in $C$ to the set $S$ .

Our goal, given a parameter $\epsilon\in(0,1)$ is to design a sparsifier:

Definition 3.

For a code $C\subseteq\{0,1\}^{m}$ , weights $w:[m]\rightarrow\mathbb{R}_{\geq 0}$ , and an accuracy parameter $\epsilon>0$ , a $(1\pm\epsilon)$ sparsifier of $C$ is a new set of weights $\widetilde{w}:[m]\rightarrow\mathbb{R}_{\geq 0}$ such that, for every $c\in C$ :

\langle\widetilde{w},c\rangle=\sum_{i=1}^{m}\widetilde{w}(i)c_{i}\in(1\pm% \epsilon)\langle w,c\rangle=\sum_{i=1}^{m}w(i)c_{i}.

The goal is to design sparsifiers which reduce the support size of the starting code; i.e., which minimize $|\operatorname{supp}(\widetilde{w})|$ .

$\blacktriangleright$ Remark 4.

Note that in some contexts, for an unweighted code $C\subseteq\{0,1\}^{m}$ , we will use $w\cdot C$ to refer to the code which assigns weight $w$ to all coordinates in $[m]$ . Similarly, for codes $C_{1}\subseteq\{0,1\}^{A_{1}}$ , $C_{2}\subseteq\{0,1\}^{A_{2}}$ with $A_{1}\cap A_{2}=\emptyset$ , we may use $w_{1}\cdot C_{1}\cup w_{2}\cdot C_{2}$ to refer to the code which assigns weights $w_{1}$ to coordinates in $A_{1}$ and $w_{2}$ to coordinates in $A_{2}$ .

For reference, we include the definitions of non-redundancy and chain length below. Note that non-redundancy essentially captures the largest diagonal matrix (after permuting the codewords) which one can find in a set of $\{0,1\}$ -valued vectors.

Definition 5.

Let $C\subseteq\{0,1\}^{m}$ be an arbitrary set of vectors. We say that the non-redundancy of $C$ (denoted $\mathrm{NRD}(C)$ ) is the largest size of a set $S\subseteq[m]$ such that for every $j\in S$ , there is a codeword $c\in C$ where $c_{j}=1$ , but for every other $i\in S\setminus\{j\}$ , $c_{i}=0$ .

Likewise, we use the notion of chain length, which is essentially the largest upper triangular submatrix contained in a set of vectors:

Definition 6.

Let $C\subseteq\{0,1\}^{m}$ be a code. A chain of length $\ell$ is a pair of injective maps $a:[\ell]\rightarrow m$ and $c:[\ell]\rightarrow C$ such that the following conditions hold:

1.

$\forall i\in[\ell]:c(i)_{a(i)}=1$
2.

$\forall 1\leq i<j\leq\ell:c(i)_{a(j)}=0$ .

The chain length of $C$ , denoted by $\mathrm{CL}(C)$ is the length of the longest chain.

Note that $\mathrm{NRD}(C)\leq\mathrm{CL}(C)$ as any diagonal matrix is trivially an upper triangular matrix. With this, we can make use of the following bound (observed in [7]):

Claim 7.

$|C|\leq(m+1)^{\mathrm{NRD}(C)}\leq(m+1)^{\mathrm{CL}(C)}$ .

2.2 Concentration Bound

We will make use of the following concentration bound when sub-sampling to construct our sparsifiers:

Claim 8.

([12]) Let $X_{1},\dots X_{\ell}$ be random variables such that $X_{i}$ takes on value $1/p_{i}$ with probability $p_{i}$ , and is $0$ otherwise. Also, suppose that $\min_{i}p_{i}\geq p$ . Then, with probability at least $1-2e^{-0.38\epsilon^{2}\ell p}$ ,

\sum_{i}X_{i}\in(1\pm\epsilon)\ell.

3 Chain Length Counting Bounds via Contractions

In this section we show the following lemma via a simple contraction argument:

Lemma 9.

Let $C\subseteq\{0,1\}^{m}$ be any code. Then, for any parameter $d>0$ , there is a set $T\subseteq[m]$ of size $|T|\leq\mathrm{CL}(C)\cdot d$ such that for any $\alpha\in\mathbb{Z}^{+}$ , the number of codewords in $C|_{\bar{T}}$ of weight $\leq\alpha d$ is at most $\binom{\mathrm{CL}(C)}{\alpha}\cdot(m+1)^{\alpha}$ .

3.1 Contractions

To start, we have the following claim which governs how the chain length of a set of vectors behaves under contractions.

Claim 10.

Let $C\subseteq\{0,1\}^{m}$ be an arbitrary set of vectors and let $i\in[m]$ be any coordinate such that there exists a $c\in C$ such that $c_{i}=1$ . Then, for $C^{\prime}=\{c\in C:c_{i}=0\}$ , we have that $\mathrm{CL}(C^{\prime})\leq\mathrm{CL}(C)-1$ .

Proof.

For the code $C^{\prime}$ , let the maps witnessing the chain length of $C^{\prime}$ be denoted by $a^{\prime},c^{\prime}$ , and let the chain length be $\ell^{\prime}$ . Now, let us define $a:[\ell^{\prime}+1]\rightarrow[m],c:[\ell^{\prime}+1]\rightarrow C$ , such that for $j\in[\ell^{\prime}],c(j)=c^{\prime}(j),a(j)=a^{\prime}(j)$ , and $a(\ell^{\prime}+1)=i$ and $c(\ell^{\prime}+1)=v$ , where $v\in C$ is any codeword such that $v_{i}\neq 0$ .

Observe that we trivially have $\forall j\in[\ell^{\prime}+1]:c(j)_{a(j)}=1$ . Likewise, because every codeword $c$ in $C^{\prime}$ satisfies $c_{i}=0$ and the first $\ell^{\prime}$ codewords mapped to by $c$ are all in $C^{\prime}$ , we also have that for any $j\in[\ell^{\prime}]$ , $c(j)_{a(\ell^{\prime}+1)}=c(j)_{i}=0$ . Together with the conditions already guaranteed by $c^{\prime},a^{\prime}$ , this yields a chain of length $\ell^{\prime}+1$ in $C$ , and thus the claim. $\hfill\vartriangleleft$

3.2 Contraction Algorithm

Leveraging the above claim which governs chain length under contractions, we define the following iterative contraction procedure:

Algorithm 1 Contract

(C,\alpha)

.

Now, let us define a new quantity:

Definition 11.

The density of a code $C\subseteq\{0,1\}^{m}$ is given by

\Phi(C)=\min_{C^{\prime}\subseteq C}\frac{|\mathrm{Supp}(C^{\prime})|}{\mathrm% {CL}(C^{\prime})},

where $\mathrm{Supp}(C^{\prime})=\{i\in[m]:\exists c\in C^{\prime}:c_{i}\neq 0\}$ .

We immediately get the following counting bound.

Claim 12.

Let $C\subseteq\{0,1\}^{m}$ be a code. Then, for any positive integer $\alpha$ , the number of codewords of weight $\leq\alpha\cdot\Phi(C)$ is $\leq\binom{\mathrm{CL}(C)}{\alpha}\cdot(m+1)^{\alpha}$ .

Proof.

Fix any codeword $c$ of weight $\leq\alpha\Phi(C)$ , and run $\mathrm{Contract}(C,\alpha)$ . For some intermediate code $C^{\prime}$ achieved during the contraction procedure, observe that if $\mathrm{CL}(C^{\prime})=k$ , then necessarily, $|\mathrm{Supp}(C^{\prime})|\geq\Phi(C)\cdot k$ . Thus, in the next random choice of $i$ , the probability that our codeword $c$ satisfies $c_{i}=1$ is at most

\frac{\mathrm{wt}(c)}{\Phi(C)\cdot k}\leq\frac{\alpha\Phi(C)}{\Phi(C)\cdot k}% \leq\frac{\alpha}{k},

and thus $c$ survives the contraction with probability $\geq 1-\frac{\alpha}{k}$ . The probability that $c$ survives all contractions until $\mathrm{CL}(C)\leq\alpha$ is thus

\geq\prod_{k=\alpha+1}^{\mathrm{CL}(C)}\left(1-\frac{\alpha}{k}\right)=\binom{% \mathrm{CL}(C)}{\alpha}^{-1}.

Conditioned on surviving, the codeword $c$ is then chosen uniformly at random among all surviving codewords, and thus returned by $\mathrm{Contract}(C,\alpha)$ with probability $\geq(m+1)^{-\alpha}$ , where we are using Claim 7 which bounds the number of codewords in a code with $\mathrm{CL}$ at most $\alpha$ . So, $c$ is returned by $\mathrm{Contract}(C,\alpha)$ with probability at least $(m+1)^{-\alpha}\cdot\binom{\mathrm{CL(C)}}{\alpha}^{-1}$ . By taking the reciprocal, this yields the bound on the number of codewords of weight $\leq\alpha\cdot\Phi(C)$ . $\hfill\vartriangleleft$

Importantly, we also have the following claim:

Claim 13.

Let $C\subseteq\{0,1\}^{m}$ be a code, and let $C^{\prime}\subseteq C$ such that $\mathrm{CL}(C^{\prime})=\ell$ . Let $T=\mathrm{Supp}(C^{\prime})$ , and let $C|_{\bar{T}}$ denote the code $C$ with the coordinates corresponding to the support of $C^{\prime}$ removed. We have:

\mathrm{CL}(C|_{\bar{T}})\leq\mathrm{CL}(C)-\ell.

Proof.

As before, let $a_{1},c_{1}$ be the functions which witness the chain length of $C|_{\bar{T}}$ , and let $a_{2},c_{2}$ be the functions which witness the chain length of $\mathrm{CL}(C^{\prime})$ . Note that $\mathrm{Im}(a_{1})\subseteq[m]-T\subseteq[m]$ and $\mathrm{Im}(a_{2})\subseteq T\subseteq[m]$ .

We define functions $a, c$ as follows: $a:[\ell+\mathrm{CL}(C|_{\bar{T}})]\rightarrow[m]$ , where $a[j],c[j]=a_{2}[j],c_{2}[j]$ if $j\leq\ell$ , and otherwise $a[j],c[j]=a_{1}[j-\ell],c_{1}[j-\ell]$ . Importantly, because for $j\in[\ell]$ , $c(j)\in C^{\prime}$ , and $a(\geq\ell)\subseteq\bar{T}$ , we have that $c(j)_{a(\geq\ell)}=0$ . The remaining conditions for chain length are then trivially satisfied by the fact that $a_{1},c_{1},a_{2},c_{2}$ already satisfied the definition of chain length individually.

Pictorially, we have:

C=\begin{bmatrix}C^{\prime}&A\\ 0&C|_{\bar{T}}\end{bmatrix},

thus we can trivially compose the upper triangular matrices corresponding to $C^{\prime},C|_{\bar{T}}$ . $\hfill\vartriangleleft$

Lemma 14.

Let $C\subseteq\{0,1\}^{m}$ be any code. Then, for any parameter $d>0$ , there is a set $T\subseteq[m]$ of size $|T|\leq\mathrm{CL}(C)\cdot d$ such that for any $\alpha\in\mathbb{Z}^{+}$ , the number of codewords in $C|_{\bar{T}}$ of weight $\leq\alpha d$ is at most $\binom{\mathrm{CL}(C)}{\alpha}\cdot(m+1)^{\alpha}$ .

Proof.

If $\Phi(C)>d$ , then we are immediately done by invoking Claim 12. Otherwise, there is some $C^{\prime}\subseteq C$ for which

\displaystyle\frac{|\mathrm{Supp}(C^{\prime})|}{\mathrm{CL}(C^{\prime})}\leq d.

(1)

So, let $T=\mathrm{Supp}(C^{\prime})$ , and let us set $C=C|_{\bar{T}}$ . Again, we can check whether $\Phi(C)>d$ , if so, we are done, and we simply return the set $T$ as is. Otherwise, there is a new subcode $C^{\prime\prime}\subseteq C$ for which $\frac{|\mathrm{Supp}(C^{\prime\prime})|}{\mathrm{CL}(C^{\prime\prime})}\leq d$ . Again, we let $T\leftarrow T\cup\mathrm{Supp}(C^{\prime\prime})$ , let $C=C|_{\bar{T}}$ and continue on recursively.

Eventually, $\Phi(C)>d$ (or the entire support of the code is removed) at which point we terminate. All that remains is to bound the size of the set $T$ . For this, every time we remove the support of a subcode $C^{\prime}$ , we increase the size of the set $T$ by at most $d\cdot\mathrm{CL}(C^{\prime})$ , as $|\mathrm{Supp}(C^{\prime})|\leq d\cdot\mathrm{CL}(C^{\prime})$ (by Equation 1). However, by Claim 13, every time we remove $\mathrm{Supp}(C^{\prime})$ from $C$ , $\mathrm{CL}(C)$ decreases by $\mathrm{CL}(C^{\prime})$ . Hence, the total number of coordinates removed in the set $T$ can be at most $d\cdot\mathrm{CL}(C)$ , before the chain length of the remaining code goes to $0$ . This yields the lemma. $\hfill\blacktriangleleft$

4 Leveraging Decomposition to Build Sparsifiers

4.1 Basic Sparsifier Construction for Unweighted Codes

A consequence of Lemma 9 is that it allows us to build sparsifiers for unweighted codes which preserve only $\widetilde{O}(\mathrm{CL}(C))$ many coordinates:

Theorem 15.

Let $C\subseteq\{0,1\}^{m}$ be an unweighted code. Then, for any $\epsilon>0$ , there exists a $(1\pm\epsilon)$ sparsifier of $C$ which preserves only

O(\mathrm{CL}(C)(\log m)^{2}(\log\log m)^{2}/\epsilon^{2})

many re-weighted coordinates.

The algorithm for achieving this sparsification is simple, and builds off of the intuition of [23, 21]. Namely, starting with a code $C\subseteq\{0,1\}^{m}$ , we invoke the decomposition of Lemma 9 with parameter $d=\sqrt{\frac{m}{\mathrm{CL}(C)}}$ . This yields two codes: $C_{\mathrm{Peel}}$ which contains the $\leq\mathrm{CL}(C)\cdot d\leq\sqrt{m\mathrm{CL}(C)}$ many coordinates that Lemma 9 peels off, along with $C_{\mathrm{remaining}}$ , which contains all remaining coordinates, with the promise that in $C_{\mathrm{remaining}}$ , for any $\alpha\in\mathbb{Z}^{+}$ , the number of codewords in $(C_{\mathrm{remaining}})|_{\bar{T}}$ of weight $\leq\alpha d$ is at most $\binom{\mathrm{CL}(C)}{\alpha}\cdot(m+1)^{\alpha}$ . We then sub-sample the coordinates of $C_{\mathrm{remaining}}$ , and then recurse. The formal algorithm is presented below.

Algorithm 2 Sparsify

(C,\epsilon,\mathrm{counter},m)

.

We now prove some basic claims regarding the above algorithm:

Claim 16.

When invoked on a code $C\subseteq\{0,1\}^{m}$ , Line 7 in Algorithm 2 is always possible.

Proof.

After performing the decomposition of Lemma 9 with parameter $d=\sqrt{\frac{m\cdot\eta}{\mathrm{CL}(C)}}$ , it must be the case that in $C_{\mathrm{remaining}}$ , for any $\alpha\in\mathbb{Z}^{+}$ , the number of codewords in $(C_{\mathrm{remaining}})$ of weight $\leq\alpha d$ is at most $\binom{\mathrm{CL}(C)}{\alpha}\cdot(m+1)^{\alpha}$ . Thus, if one randomly samples the coordinates of $C_{\mathrm{remaining}}$ at rate $p=\sqrt{\frac{\eta\mathrm{CL}(C)}{m}}$ , and assigns weight $1/p$ to the sampled coordinates a simple Chernoff and union bound will show that every codeword’s weight is preserved to a $(1\pm\epsilon/20\log\log(m))$ factor with probability $1-1/\mathrm{poly}(m)$ . Indeed, for a fixed value of $\alpha$ , a codeword of weight $\in[\alpha d,2\alpha d]$ will have its weight preserved to within a $(1\pm\epsilon/20\log\log(m))$ factor with probability (using Claim 8) at least

	$\displaystyle 1-2e^{-0.38(\epsilon/20\log\log(m))^{2}\cdot\alpha d\cdot\sqrt{% \frac{\eta\mathrm{CL}(C)}{m}}}$	$\displaystyle\geq 1-2e^{-0.38(\epsilon/20\log\log(m))^{2}\cdot\alpha\eta}$
		$\displaystyle\geq 1-2e^{-0.38\cdot\alpha\cdot 1000\log(m)}$
		$\displaystyle\geq 1-\frac{1}{m^{100\alpha}}.$

Then, we can take a union bound over all codewords of weight $\leq 2\alpha d$ , at most $\binom{\mathrm{CL}(C)}{2\alpha}\cdot(m+1)^{2\alpha}\leq(m+1)^{4\alpha}$ of them, and then a union bound over the at most $m$ choices of $\alpha$ to conclude that every codeword has its weight preserved to a $(1\pm\epsilon/(20\log\log(m)))$ factor with probability $1-\frac{1}{m^{95}}$ (in particular such a sparsification exists).

At the same time, a Chernoff bound will show that when sampling at this rate, with probability $\Omega(1)$ , at most $2\cdot\sqrt{\mathrm{CL}(C)\cdot\eta\cdot m}$ many coordinates will survive the sampling, and thus there exists a set of coordinates $|\widetilde{T}|\leq 2\sqrt{\mathrm{CL}(C)\cdot\eta\cdot m}$ , and weight $w\in\mathbb{R}$ such that $w\cdot C_{\widetilde{T}}$ is a $(1\pm\epsilon/(20\log\log(n))$ code sparsifier of $C_{\mathrm{Remaining}}$ . $\hfill\vartriangleleft$

Claim 17.

When invoked on a code $C\subseteq\{0,1\}^{m}$ , $w\cdot C_{\widetilde{T}}\cup C_{\mathrm{Peel}}$ as produced in Line 7 is a $(1\pm\epsilon/20\log\log(m))$ code sparsifier of $C$ .

Proof.

This follows because $C_{\bar{T}}\cup C_{\mathrm{Peel}}$ is a perfect sparsifier of $C$ . Then, when replacing $C_{\bar{T}}$ with a $(1\pm\epsilon/20\log\log(m))$ sparsifier of $C_{\bar{T}}$ , it follows by composition that the resulting code is a $(1\pm\epsilon/20\log\log(m))$ code sparsifier of $C$ . $\hfill\vartriangleleft$

Claim 18.

Let $C\subseteq\{0,1\}^{m}$ be a code and let $\epsilon>0$ . Then $\mathrm{Sparsify}(C,\epsilon,0)$ returns a code $\widetilde{C}$ which is a $(1\pm\epsilon)$ sparsifier of $C$ .

Proof.

This follows by induction over the value of $\mathrm{Counter}$ . Indeed, when sparsifying the code $C$ , we consider all the resulting codes for which $\mathrm{Sparsify}$ is recursively called. We let $w_{i,1}\cdot C^{(i)}_{1},\dots w_{i,2^{i}}\cdot C^{(i)}_{2^{i}}$ denote all $2^{i}$ codes for which the $\mathrm{Sparsify}$ function is called with $\mathrm{Counter}=i$ . We inductively claim that $w_{i,1}\cdot C^{(i)}_{1}\cup\dots\cup w_{i,2^{i}}\cdot C^{(i)}_{2^{i}}$ is a $(1\pm 3i\epsilon/20\log\log(m))$ sparsifier of $C$ .

The base case follows trivially, using Claim 17.

The inductive case follows by observing that for each code $w_{i,j}\cdot C^{(i)}_{j}$ , by invoking Claim 17, we replace $C^{(i)}_{j}$ by two codes $w_{i+1,2j}C^{(i+1)}_{2j}$ and $w_{i+1,2j+1}\cdot C^{(i)}_{2j+1}$ such that

w_{i+1,2j}C^{(i+1)}_{2j}\cup w_{i+1,2j+1}\cdot C^{(i)}_{2j+1}

is a $(1\pm\epsilon/20\log\log(m))$ sparsifier of $w_{i,j}\cdot C^{(i)}_{j}$ . By composition over all the codes $w_{i,1}\cdot C^{(i)}_{1}\cup\dots\cup w_{i,2^{i}}\cdot C^{(i)}_{2^{i}}$ , it follows then that

w_{i+1,1}\cdot C^{(i+1)}_{1}\cup\dots\cup w_{i+1,2^{i+1}}\cdot C^{(i+1)}_{2^{i% +1}}

will be a $(1\pm\epsilon/20\log\log(m))\cdot(1\pm 3\epsilon i/20\log\log(m))\in(1\pm 3% \epsilon(i+1)/20\log\log(m))$ -sparsifier.

Taking $i=\log\log(m)$ yields our desired claim. $\hfill\vartriangleleft$

Claim 19.

Let $C\subseteq\{0,1\}^{m}$ be a code and let $\epsilon>0$ . Then $\mathrm{Sparsify}(C,\epsilon,0)$ returns a code $\widetilde{C}$ which retains only $O\left(\frac{\mathrm{CL}(C)\log^{2}(m)(\log\log(m))^{2}}{\epsilon^{2}}\right)$ many coordinates.

Proof.

We claim that whenever $\mathrm{Sparsify}$ is invoked on a code $C^{\prime}$ with $\mathrm{Counter}=i$ , then

|\mathrm{Supp}(C^{\prime})|\leq 4\cdot\mathrm{CL}(C)\cdot\left(\frac{m}{% \mathrm{CL}(C)}\right)^{1/2^{i}}\cdot\eta.

The base case follows trivially: indeed, in the first invocation ( $i=1$ ) of the algorithm, $|\mathrm{Supp}(C_{\mathrm{Peel}})|\leq\mathrm{CL}(C)\cdot\sqrt{\frac{m\cdot% \eta}{\mathrm{CL}(C)}}$ which trivially satisfies the above bound, and $|\mathrm{Supp}(C_{\widetilde{T}})|\leq 2\sqrt{\mathrm{CL}(C)\cdot m\cdot\eta}% \leq 2\cdot\mathrm{CL}(C)\cdot\sqrt{\frac{m}{\mathrm{CL}(C)}}\cdot\eta$ , which also trivially satisfies the above bound. Now, we assume the claim holds by induction.

Then, at level $i$ of the algorithm

|\mathrm{Supp}(C^{\prime})|\leq 4\mathrm{CL}(C)\cdot\left(\frac{m}{\mathrm{CL}% (C)}\right)^{1/2^{i}}\cdot\eta.

When we sparsify $C^{\prime}$ , we obtain two codes, $C^{\prime}_{\mathrm{Peel}}$ and $C^{\prime}_{\widetilde{T^{\prime}}}$ . We have that (by our choice of $d$ in Algorithm 2)

|\mathrm{Supp}(C^{\prime}_{\mathrm{Peel}})|\leq\mathrm{CL}(C)\cdot\sqrt{\frac{% 4\mathrm{CL}(C)\cdot\left(\frac{m}{\mathrm{CL}(C)}\right)^{1/2^{i}}\cdot\eta% \cdot\eta}{\mathrm{CL}(C)}}\leq 4\mathrm{CL}(C)\cdot\eta\cdot\left(\frac{m}{% \mathrm{CL}(C)}\right)^{1/2^{i+1}},

as we desire. Likewise,

|\mathrm{Supp}(C^{\prime}_{\widetilde{T^{\prime}}})|\leq 2\sqrt{\mathrm{CL}(C)% \cdot 4\mathrm{CL}(C)\cdot\left(\frac{m}{\mathrm{CL}(C)}\right)^{1/2^{i}}\cdot% \eta\cdot\eta}\leq 4\mathrm{CL}(C)\cdot\eta\cdot\left(\frac{m}{\mathrm{CL}(C)}% \right)^{1/2^{i+1}}

\leq 4\mathrm{CL}(C)\cdot\eta\cdot\left(\frac{m}{\mathrm{CL}(C)}\right)^{1/2^{% i+1}},

as we desire.

Now, once $i=\log\log(m)$ , we have that

|\mathrm{Supp}(C^{\prime})|\leq 4\mathrm{CL}(C)\cdot\left(\frac{m}{\mathrm{CL}% (C)}\right)^{1/2^{\log\log(m)}}\cdot\eta\leq 8\mathrm{CL}(C)\cdot\eta.

Thus, the returned code $\widetilde{C}$ is the union of $\leq 2^{\log\log(m)}=\log(m)$ many codes, each of which retains $\leq 8\mathrm{CL}(C)\cdot\eta$ many coordinates. Thus, the total sparsifier size is bounded by

\log(m)\cdot 8\mathrm{CL}(C)\cdot\eta=O\left(\frac{\mathrm{CL}(C)\log^{2}(m)(% \log\log(m))^{2}}{\epsilon^{2}}\right),

as we desire. $\hfill\vartriangleleft$

Together, these above claims give the following theorem:

Theorem 20.

For a code $C\subseteq\{0,1\}^{m}$ and $\epsilon>0$ , there exists a $(1\pm\epsilon)$ code sparsifier of $C$ which retains only $O\left(\frac{\mathrm{CL}(C)\log^{2}(m)(\log\log(m))^{2}}{\epsilon^{2}}\right)$ many coordinates.

Proof.

We invoke Algorithm 2. The accuracy of the sparsifier follows from Claim 18 and the size follows from Claim 19. $\hfill\blacktriangleleft$

Note that at this point, one can use Theorem 20 along with weighted to unweighted sparsifier reduction frameworks as in [23, 21, 7] to deduce sparsifiers for weighted codes which preserve $O\left(\frac{\mathrm{CL}(C)\log^{2}(m)(\log\log(m))^{2}}{\epsilon^{2}}\right)$ many coordinates.

Corollary 21.

For a code $C\subseteq\{0,1\}^{m}$ , weights $w:[m]\rightarrow\mathbb{R}_{\geq 0}$ and $\epsilon>0$ , there exists a $(1\pm\epsilon)$ code sparsifier of $C$ which retains only $O\left(\frac{\mathrm{CL}(C)\log^{2}(m)(\log\log(m))^{2}}{\epsilon^{2}}\right)$ many coordinates.

For completeness, we include a proof of Corollary 21 in Appendix A.

4.2 Dimension-Free Bounds

In this section, we show that the dependence on $\log(m)$ can be removed, and instead replaced with dependence only on $\log(\mathrm{CL})$ , thus constituting a dimension-free sparsification result. To do this, we merely repeatedly apply the sparsification result of Corollary 21:

Theorem 22.

For a code $C\subseteq\{0,1\}^{m}$ , weights $w:[m]\rightarrow\mathbb{R}_{\geq 0}$ and $\epsilon>0$ , there exists a $(1\pm\epsilon)$ code sparsifier of $C$ which retains only

O\left(\frac{\mathrm{CL}(C)\cdot\log^{2}(\mathrm{CL}(C)/\epsilon)\cdot\log\log% (\mathrm{CL}(C)/\epsilon)^{2}}{\epsilon^{2}}\right)

many coordinates.

Proof.

First, let us use $K$ to denote the hidden constant in the $O(\cdot)$ notation above. In the below, we assume that $m$ is at least a sufficiently large constant to begin with. Now, we consider two cases:

1.

When $m\geq 2^{\mathrm{CL}(C)/(\epsilon^{2})}$ , then after applying Corollary 21 with $\epsilon^{\prime}=\epsilon/Q\log m$ (for a large constant $Q$ ), we obtain a $(1\pm\epsilon^{\prime})$ sparsifier of $C$ with support $\leq\frac{K\cdot\mathrm{CL}(C)\cdot\log^{4}(m)\cdot\log\log(m)^{2}}{\epsilon^{% 2}}\leq\log^{6}(m)$ .
2.

When $m<2^{\mathrm{CL}(C)/(\epsilon^{2})}$ , we sparsify $C$ once with parameter $\epsilon^{\prime}=\epsilon/Q\log(m)$ , obtaining a code $C^{\prime}$ which is a $(1\pm\epsilon^{\prime})$ sparsifier of $C$ with support $\leq\frac{K\cdot\mathrm{CL}(C)\cdot\log^{4}(m)\cdot\log\log(m)^{2}}{\epsilon^{% 2}}\leq K\cdot\mathrm{CL}(C)^{7}/\epsilon^{14}$ . Then, we sparsify $C^{\prime}$ with parameter $\epsilon/2$ , and obtain a code $C^{\prime\prime}$ which is a $(1\pm\epsilon/2)$ sparsifier of $C^{\prime}$ , and retains at most

$\frac{K\cdot\mathrm{CL}(C)\cdot\log^{2}(\mathrm{CL}(C)/\epsilon)\cdot\log\log(% \mathrm{CL}(C)/\epsilon)^{2}}{\epsilon^{2}}$

many coordinates.

Thus, given an arbitrary codes $C$ , we apply case (1) $\ell=O(\log^{*}(m))$ many times, yielding code $C^{(1)},\dots C^{(\ell)}$ . Then, we apply case (2) to $C^{(\ell)}$ , yielding a code $C^{\prime\prime}$ which retains only

\leq\frac{K\cdot\mathrm{CL}(C)\cdot\log^{2}(\mathrm{CL}(C)/\epsilon)\cdot\log% \log(\mathrm{CL}(C)/\epsilon)^{2}}{\epsilon^{2}}

many coordinates.

All that remains is to show that $C^{\prime\prime}$ is a $(1\pm\epsilon)$ sparsifier of $C$ . This follows by composition of the sparsifier accuracy: we let $m^{(i)}$ denote the support size of the $i$ th sparsifier we create in the above chain (with $m^{(0)}$ being the starting value of $m$ ). Then, $C^{(1)}$ is a $(1\pm\epsilon/Q\log(m^{(0)}))$ sparsifier of $C$ , $C^{(2)}$ is a $(1\pm\epsilon/\log(m^{(1)}))$ sparsifier of $C^{(1)}$ , and so on. In particular, this implies that $C^{(\ell)}$ is a

\prod_{i=0}^{\ell-1}(1\pm\epsilon/Q\log(m^{(i)}))

sparsifier of $C$ . Thus $C^{(\ell)}$ is a

\left(1\pm\epsilon\cdot O\left(\sum_{i=0}^{\ell-1}\frac{1}{Q\cdot\log(m^{(i)})% }\right)\right)=\left(1\pm\epsilon/10\right)

sparsifier of $C$ , where we have chosen $Q$ to be a large enough constant. In particular, here we are using the fact that, letting $q=\log(m^{(\ell-1)})$ ,

\sum_{i=0}^{\ell-1}\frac{1}{\log(m^{(i)})}\leq\frac{1}{q}+\frac{1}{2^{q^{1/6}}% }+\frac{1}{2^{\left(2^{q^{1/6}}\right)^{1/6}}}+\dots=O(1/q)=O(1).

This relation follows from the fact that $m^{(i)}\leq\log^{6}(m^{(i-1)})$ as established above.

Now $C^{\prime}$ is a $(1\pm\epsilon/Q)$ sparsifier of $C^{(\ell)}$ , which implies that $C^{\prime}$ is a $(1\pm\epsilon/10)\cdot(1\pm\epsilon/Q)\in(1\pm\epsilon/4)$ sparsifier of $C$ .

Finally, $C^{\prime\prime}$ is a $(1\pm\epsilon/2)$ sparsifier of $C^{\prime}$ , and thus by composition, $C^{\prime\prime}$ is a $(1\pm\epsilon)$ sparsifier of $C$ , as we desire (note, here we are using that $\epsilon$ is a sufficiently small constant). $\hfill\blacktriangleleft$

5 Conclusion

In this paper, we constructed sparsifiers for arbitrary set systems of near-optimal size. In particular, we simplify the proof strategy of Brakensiek and Guruswami [7] by presenting a contraction-based counting bound which results in an overall simpler proof in addition to better asymptotics. Furthermore, by recursively applying our sparsifier, our bound only depends on the accuracy $\epsilon$ and the chain length of the underlying set system. We conclude this paper with an exciting open direction and our conjecture regarding it.

Truly linear sparsifiers.

A celebrated result of Batson, Spielman and Srivastava [3] states that graphs on $n$ vertices have $(1\pm\epsilon)$ cut sparsifiers with $O(n/\epsilon^{2})$ -edges. Furthermore, such asymptotics are known to be tight up to a constant factor [9]. Proving an analogue of [3] for arbitrary set systems seems quite difficult as there is no clear spectral analogue of set system sparsification (however, see [22]). Currently, the most general extensions of [3] are to the regime of PSD matrix sparsification in the work of [27] (which even includes arity $3$ hypergraph cut sparsification). Nonetheless, we boldly conjecture that analogous constructions should exist in general.

Conjecture 23.

For a set system $\mathcal{S}\subseteq 2^{[m]}$ , weights $w:[m]\rightarrow\mathbb{R}_{\geq 0}$ and $\epsilon>0$ , there exists a $(1\pm\epsilon)$ sparsifier of $\mathcal{S}$ which retains only

O\left(\frac{\mathrm{CL}(\mathcal{S})}{\epsilon^{2}}\right)

many coordinates.

Of note, even proving Conjecture 23 for linear code sparsification would be a significant result.

References

[1] Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, Cambridge, 1999.
[2] Arpon Basu, Pravesh K. Kothari, Yang P. Liu, and Raghu Meka. Sparsifying sums of positive semidefinite matrices. In Kasper Green Larsen and Barna Saha, editors, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 6042–6064. SIAM, 2026. doi:10.1137/1.9781611978971.216.
[3] Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice-Ramanujan sparsifiers. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 255–262. ACM, 2009. doi:10.1145/1536414.1536451.
[4] András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Õ(n ${}^{\mbox{2}}$ ) time. In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 47–55. ACM, 1996. doi:10.1145/237814.237827.
[5] Christian Bessiere, Clément Carbonnel, and George Katsirelos. Chain Length and CSPs Learnable with Few Queries. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02):1420–1427, April 2020. doi:10.1609/aaai.v34i02.5499.
[6] Christian Bessiere, Remi Coletta, Emmanuel Hebrard, George Katsirelos, Nadjib Lazaar, Nina Narodytska, Claude-Guy Quimper, and Toby Walsh. Constraint acquisition via partial queries. In Francesca Rossi, editor, IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, pages 475–481. IJCAI/AAAI, 2013. URL: http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6659.
[7] Joshua Brakensiek and Venkatesan Guruswami. Redundancy is all you need. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 1614–1625. ACM, 2025. doi:10.1145/3717823.3718212.
[8] Silvia Butti and Stanislav Živný. Sparsification of Binary CSPs. SIAM Journal on Discrete Mathematics, 34(1):825–842, January 2020. doi:10.1137/19M1242446.
[9] Charles Carlson, Alexandra Kolla, Nikhil Srivastava, and Luca Trevisan. Optimal lower bounds for sketching graph cuts. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2565–2569. SIAM, 2019. doi:10.1137/1.9781611975482.158.
[10] Yu Chen, Sanjeev Khanna, and Ansh Nagda. Near-linear size hypergraph cut sparsifiers. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 61–72. IEEE, 2020. doi:10.1109/FOCS46700.2020.00015.
[11] Arnold Filtser and Robert Krauthgamer. Sparsification of two-variable valued constraint satisfaction problems. SIAM J. Discret. Math., 31(2):1263–1276, 2017. doi:10.1137/15M1046186.
[12] Wai Shing Fung, Ramesh Hariharan, Nicholas J.A. Harvey, and Debmalya Panigrahi. A general framework for graph sparsification. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, pages 71–80, New York, NY, USA, 2011. Association for Computing Machinery. doi:10.1145/1993636.1993647.
[13] Mohsen Ghaffari, David R. Karger, and Debmalya Panigrahi. Random contractions and sampling for hypergraph and hedge connectivity. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1101–1114. SIAM, 2017. doi:10.1137/1.9781611974782.71.
[14] Justin Gilmer. A constant lower bound for the union-closed sets conjecture. arXiv preprint, 2022. arXiv:2211.09055.
[15] Jun-Ting Hsieh, Daniel Z. Lee, Sidhanth Mohanty, Aaron Putterman, and Rachel Yun Zhang. Sparsifying cayley graphs on every group. In Kasper Green Larsen and Barna Saha, editors, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 6029–6041. SIAM, 2026. doi:10.1137/1.9781611978971.215.
[16] Arun Jambulapati, Yang P Liu, and Aaron Sidford. Chaining, group leverage score overestimates, and fast spectral hypergraph sparsification. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 196–206, 2023. doi:10.1145/3564246.3585136.
[17] Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida. Spectral hypergraph sparsifiers of nearly linear size. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1159–1170. IEEE, 2021. doi:10.1109/FOCS52979.2021.00114.
[18] Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida. Towards tight bounds for spectral sparsification of hypergraphs. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 598–611, 2021. doi:10.1145/3406325.3451061.
[19] David R. Karger. Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm. In Vijaya Ramachandran, editor, Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 25-27 January 1993, Austin, Texas, USA, pages 21–30. ACM/SIAM, 1993. URL: http://dl.acm.org/citation.cfm?id=313559.313605.
[20] Sanjeev Khanna, Aaron Putterman, and Madhu Sudan. Near-optimal size linear sketches for hypergraph cut sparsifiers. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1669–1706. IEEE, 2024. doi:10.1109/FOCS61266.2024.00105.
[21] Sanjeev Khanna, Aaron Putterman, and Madhu Sudan. Efficient algorithms and new characterizations for CSP sparsification. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 407–416. ACM, 2025. doi:10.1145/3717823.3718205.
[22] Sanjeev Khanna, Aaron Putterman, and Madhu Sudan. A theory of spectral CSP sparsification. arXiv preprint, 2025. doi:10.48550/arXiv.2504.16206.
[23] Sanjeev Khanna, Aaron (Louie) Putterman, and Madhu Sudan. Code sparsification and its applications. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 5145–5168. SIAM, 2024. doi:10.1137/1.9781611977912.185.
[24] Dmitry Kogan and Robert Krauthgamer. Sketching cuts in graphs and hypergraphs. In Tim Roughgarden, editor, Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 367–376. ACM, 2015. doi:10.1145/2688073.2688093.
[25] James R. Lee. Spectral hypergraph sparsification via chaining. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 207–218. ACM, 2023. doi:10.1145/3564246.3585165.
[26] Yi Li, Philip M. Long, and Aravind Srinivasan. Improved bounds on the sample complexity of learning. Journal of Computer and System Sciences, 62(3):516–527, 2001. doi:10.1006/jcss.2000.1741.
[27] Marcel K De Carli Silva, Nicholas JA Harvey, and Cristiane M Sato. Sparse sums of positive semidefinite matrices. ACM Transactions on Algorithms (TALG), 12(1):1–17, 2015. doi:10.1145/2746241.
[28] Tasuku Soma and Yuichi Yoshida. Spectral sparsification of hypergraphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2570–2581. SIAM, 2019. doi:10.1137/1.9781611975482.159.
[29] V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16:264–280, 1971.

Appendix A Proof of Corollary 21

The specific method we use for proving Corollary 21 closely follows the methodology in Section 8 of [7] (cf. Theorem 8.4). To start, we prove a version of this corollary in the setting where all the weights are bounded:

Corollary 24.

For a code $C\subseteq\{0,1\}^{m}$ , weights $w:[m]\rightarrow\mathbb{R}_{\geq 0}$ such that $w(i)\leq m^{3}$ and $\epsilon>0$ , there exists a $(1\pm\epsilon)$ code sparsifier of $C$ which retains only $O\left(\frac{\mathrm{CL}(C)\log^{2}(m)(\log\log(m))^{2}}{\epsilon^{2}}\right)$ many coordinates.

Proof.

We adapt the proof of Lemma 8.15 in [7]. First, if $\epsilon\leq 1/\sqrt{m}$ , then we simply return all the coordinates of the code $C$ , as $m\leq 1/\epsilon^{2}$ . So, for the rest of the proof, we assume that $\epsilon>1/\sqrt{m}$ . We will also assume that $\min_{i}w(i)=1$ , as otherwise we can simply rescale the weights by $\min_{i}w(i)$ to ensure this is the case (if the min weight is $0$ , we can simply delete these coordinates).

The key intuition is now that the weights are bounded, we will simply duplicate the coordinates of the code a number of times proportional to their weight, thus transforming the weighted code into an unweighted code. With this unweighted code, we can then invoke Theorem 20.

To make this unweighted code for each $i\in[m]$ , we define $b(i)=\lfloor\frac{2w(i)}{\epsilon}\rfloor\leq 2m^{4}$ to be the number of times we duplicate coordinate $i$ . Thus, we create a new code $\widetilde{C}\subseteq\{0,1\}^{\widetilde{m}}$ where $\widetilde{m}=\sum_{i=1}^{m}b(i)$ where coordinate $i$ of $C$ is replaced with $b(i)$ unweighted copies in $\widetilde{C}$ . Now, we claim that for any codeword $c\in C$ , its corresponding version $\widetilde{c}$ satisfies $\frac{\epsilon}{2}\cdot\sum_{i=1}^{\widetilde{m}}\widetilde{c}_{i}\in(1\pm% \epsilon/2)\cdot\sum_{i=1}^{m}w(i)c_{i}$ . Indeed, this follows because

\frac{\epsilon}{2}\cdot\sum_{i=1}^{\widetilde{m}}\widetilde{c}_{i}=\sum_{i=1}^% {m}\frac{\epsilon}{2}\cdot\Bigl\lfloor\frac{2w(i)}{\epsilon}\Bigr\rfloor\cdot c% _{i}\in\sum_{i=1}^{m}\frac{\epsilon}{2}\cdot\left[\frac{2w(i)}{\epsilon}-1,% \frac{2w(i)}{\epsilon}\right]\cdot c_{i}

\in\sum_{i=1}^{m}[1-\epsilon/2,1]\cdot w_{i}\cdot c_{i}\in(1\pm\epsilon/2)% \cdot\sum_{i=1}^{m}w(i)c_{i}.

Thus, to conclude the proof, we must only construct this now unweighted code $\widetilde{C}$ , sparsify it to accuracy $(1\pm\epsilon/3)$ using Theorem 20 to create a new, weighted code $\widehat{C}$ , and then return $\frac{\epsilon}{2}\cdot\widehat{C}$ . By the composition of sparsifier accuracy, this will be a $(1\pm\epsilon/2)(1\pm\epsilon/3)$ sparsifier of $C$ , which constitutes a $(1\pm\epsilon)$ sparsifier. The number of coordinates retained in the sparsifier is bounded by $O\left(\frac{\mathrm{CL}(C)\log^{2}(m)(\log\log(m))^{2}}{\epsilon^{2}}\right)$ , as we are sparsifying a code with $\widetilde{m}=\mathrm{poly}(m)$ many coordinates. $\hfill\blacktriangleleft$

With this corollary established, we can now proceed to creating sparsifiers for codes with arbitrary weights.

Proof of Corollary 21.

We fix the code $C\subseteq\{0,1\}^{m}$ , the weights $w:[m]\to\mathbb{R}_{>0}$ , and $\epsilon\in(0,1)$ . We assume WLOG that $\mathrm{CL}(C)\geq 1$ and that $\epsilon\geq 8/\sqrt{m}$ (otherwise, the code $C$ already satisfies the desired size bound).

We group the coordinates $[m]$ according to their weights. Borrowing notation from the proof of Theorem 8.4 of [7], we define a function $t:[m]\to\mathbb{Z}$ such that

t(i):=\left\lfloor\frac{\log w(i)}{3\log m}\right\rfloor,

and for each coordinate $i\in[m]$ , we assign its group to be $t(i)$ . For all $t\in\mathbb{Z}$ , we let $I_{t}\subseteq[n]$ denote the set of all coordinates in group $t$ . For each codeword $c\in C$ , we then say that the type of the codeword is the maximum group for any of its nonzero coordinates, i.e.,

\mathrm{type}(c):=\max_{i\in\operatorname{supp}(c)}t(i).

For all $t\in\mathbb{Z}$ , we let $C_{t}$ denote the set of all $c\in C$ with type $t$ .

The key observation, as used in [23, 21, 7] is that one must only consider sparsifying a codeword $c\in C_{t}$ with respect to the coordinates $I_{t}$ ; this is because the vast majority of its weight is contained in these coordinates. Furthermore, within the set of coordinates $I_{t}$ , all weights are related by a factor of at most $m^{3}$ .

Define $t\in\mathbb{Z}$ to be proper if there exists $z\in(C_{t}\cup C_{t+1})|_{I_{t}}$ which has at least one coordinate equal to $1$ . For proper $t\in\mathbb{Z}$ , let $\widetilde{w}_{t}:[m]\to\mathbb{R}_{\geq 0}$ be an $(\epsilon/2)$ -sparsifier of $(C_{t}\cup C_{t+1})|_{I_{t}}\cup\{\mathbf{1}[\operatorname{supp}(I_{t})]\}$ . Note that $\mathrm{CL}(C_{t}\cup C_{t+1})|_{I_{t}}\cup\{\mathbf{1}[\operatorname{supp}(I_% {t})]\})\geq 1$ , so

	$\displaystyle\mathrm{CL}((C_{t}\cup C_{t+1})\|_{I_{t}}\cup\{\mathbf{1}[% \operatorname{supp}(I_{t})]\})$	$\displaystyle\leq\mathrm{CL}(C_{t}\cup C_{t+1})\|_{I_{t}}\cup\{\mathbf{1}[% \operatorname{supp}(I_{t})]\})+1$
		$\displaystyle\leq 2\mathrm{CL}(C_{t}\cup C_{t+1})\|_{I_{t}}\cup\{\mathbf{1}[% \operatorname{supp}(I_{t})]\}).$

Thus, by Corollary 24, we can ensure that

\displaystyle\left|{\operatorname{supp}(\widetilde{w}_{t})}\right|\leq O\left(% \mathrm{CL}((C_{t}\cup C_{t+1})|_{I_{t}})\log^{2}(m)\log\log(m)^{2}/\epsilon^{% 2}\right).

(2)

Let $\widetilde{w}:[m]\to\mathbb{R}_{\geq 0}$ be the sum of these sparsifiers $\{\widetilde{w}_{t}:t\in\mathbb{Z},t\text{ proper}\}$ . This is well-defined as any coordinate appears in exactly one $I_{t}$ and thus can be nonzero for only $\widetilde{w}_{t}$ . It remains only to show that $\widetilde{w}$ is indeed a $(1\pm\epsilon)$ sparsifier for $C$ with weights $w$ and that it satisfies our desired sparsity bound. Adapting a computation of [7], we have for all $c\in C$ with $t:=\mathrm{type}(c)$ that

	$\displaystyle\langle\widetilde{w},c\rangle$	$\displaystyle=\langle\widetilde{w}_{t-1},c\|_{I_{t-1}}\rangle+\langle\widetilde% {w}_{t},c\|_{I_{t}}\rangle+\sum_{t^{\prime}\leq t-2}\langle\widetilde{w}_{t^{% \prime}},c\|_{I_{t^{\prime}}}\rangle$
		$\displaystyle\in[1-\epsilon/2,1+\epsilon/2]\cdot\sum_{i\in I_{t-1}\cup I_{t}}w% (i)c_{i}+\sum_{t^{\prime}\leq t-2}\langle\widetilde{w}_{t^{\prime}},c\|_{I_{t^{% \prime}}}\rangle$
		$\displaystyle=[1-\epsilon/2,1+\epsilon/2]\cdot\left[\langle w,c\rangle-\sum_{i% \in\operatorname{supp}(c)\setminus(I_{t-1}\cup I_{t})}w(i)\right]+\sum_{t^{% \prime}\leq t-2}\langle\widetilde{w}_{t^{\prime}},c\|_{I_{t^{\prime}}}\rangle.$

First, we argue that $\sum_{t^{\prime}\leq t-2}\langle\widetilde{w}_{t^{\prime}},c|_{I_{t^{\prime}}}\rangle$ is small. For this, suppose for the sake of contradiction that for some $t^{\prime}\leq t-2$ , there is a choice of $i\in I_{t^{\prime}}$ such that $\widetilde{w}(i)\geq 2m^{3t^{\prime}+4}$ . Then, observe that for the codeword $\mathbf{1}[\operatorname{supp}(I_{t^{\prime}})]$ , its weight reported by the sparsifier for $I_{t^{\prime}}$ is at least $2m^{3t^{\prime}+4}$ , which is $\geq 2\cdot\sum_{i\in I_{t^{\prime}}}w(i)$ , as each $w(i)\leq m^{3t^{\prime}+3}$ (and $|I_{t^{\prime}}|\leq m$ ). Thus, for this codeword $\mathbf{1}[\operatorname{supp}(I_{t^{\prime}})]$ , $\widetilde{w}$ restricted to $I_{t^{\prime}}$ (i.e,. $\widetilde{w}_{t^{\prime}}$ ) would not have been a $(1\pm\epsilon)$ sparsifier. So, we see that $\widetilde{w}(i)\leq 2m^{3t^{\prime}+4}$ for each $i\in I_{t^{\prime}}$ , and thus

\sum_{t^{\prime}\leq t-2}\langle\widetilde{w}_{t^{\prime}},c|_{I_{t^{\prime}}}% \rangle\leq m\cdot 2m^{3t^{\prime}+4}\leq 2m^{3t^{\prime}+5}\leq 2m^{3t-1}.

Since $t=\mathrm{type}(c)$ , we have that $\langle w,c\rangle\geq m^{3t}$ . This immediately implies that $\sum_{t^{\prime}\leq t-2}\langle\widetilde{w}_{t^{\prime}},c|_{I_{t^{\prime}}}% \rangle\leq\frac{2}{m}\cdot\langle w,c\rangle\leq\frac{\epsilon}{4}\cdot% \langle w,c\rangle$ since $\epsilon\geq 8/\sqrt{m}$ .

Further, for all $i\in\operatorname{supp}(c)\setminus(I_{t-1}\cup I_{t})$ , we have that $w(i)<m^{3t-3}$ . Therefore, the total contribution of $w(i)$ for $i\in\operatorname{supp}(c)\setminus(I_{t-1}\cup I_{t})$ is at most $m\cdot m^{3t-3}\leq\frac{\epsilon}{4}\langle w,c\rangle$ . So,

\displaystyle\langle\widetilde{w},c\rangle

\displaystyle\in[1-\epsilon/2,1+\epsilon/2]\cdot[1-\epsilon/4,1]\cdot\langle w% ,c\rangle+[0,\epsilon/4]\cdot\langle w,c\rangle\subseteq[1-\epsilon,1+\epsilon% ]\langle w,c\rangle,

as desired. It thus suffices to bound $\left|{\operatorname{supp}(\widetilde{w})}\right|$ . By (Equation 2), we have that

\displaystyle\left|{\operatorname{supp}(\widetilde{w})}\right|\leq\sum_{t\text% { proper}}\left|{\operatorname{supp}(\widetilde{w}_{t})}\right|\leq\sum_{t\in% \mathbb{Z}}O\left(\mathrm{CL}((C_{t}\cup C_{t+1})|_{I_{t}})\log^{2}(m)\log\log% (m)^{2}/\epsilon^{2}\right).

(3)

Analogous to Claim 8.16 of [7], we claim that

\sum_{t\in\mathbb{Z}}\mathrm{CL}((C_{t}\cup C_{t+1})|_{I_{t}})\leq 2\mathrm{CL% }(C).

To see this, let $A_{1},\dots A_{\ell}\subseteq I_{1},\dots I_{\ell}$ and $B_{1},\dots B_{\ell}\subseteq(C_{1}\cup C_{2}),(C_{2}\cup C_{3})\dots(C_{\ell}% ,C_{\ell+1})$ denote witnesses for the chain lengths of $\mathrm{CL}((C_{t}\cup C_{t+1})|_{I_{t}}):t\in[\ell]$ . The key observation is that $A_{\mathrm{odd}}=A_{1}\cup A_{3}\cup A_{5}\cup\dots,B_{\mathrm{odd}}=B_{1}\cup B% _{3}\cup B_{5}\cup\dots$ and $A_{\mathrm{even}}=A_{2}\cup A_{4}\cup A_{6}\cup\dots,B_{\mathrm{even}}=B_{2}% \cup B_{4}\cup B_{6}\cup\dots$ are both valid witnesses of the chain length of $C$ . To see why, we observe that because $B_{i}\subseteq C_{i}\cup C_{i+1}$ , it must be the case that every codeword $c\in B_{i}$ satisfies $c|_{I_{\geq i+2}}=0$ . Thus, for any coordinate $p\in A_{\geq i+2}$ , we see that $c_{p}=0$ . Importantly then, because $A_{i},B_{i}$ is a chain, and $A_{i+2},B_{i+2}$ is defined on a disjoint support, their concatenation still remains a chain as per Claim 13.

With this, we then immediately have that

\sum_{t}\mathrm{CL}((C_{t}\cup C_{t+1})|_{I_{t}})=\sum_{t:t=0\!\!\!\!\mod 2}% \mathrm{CL}((C_{t}\cup C_{t+1})|_{I_{t}})+\sum_{t:t=1\!\!\!\!\mod 2}\mathrm{CL% }((C_{t}\cup C_{t+1})|_{I_{t}})

\leq\mathrm{CL}(C)+\mathrm{CL}(C)\leq 2\mathrm{CL}(C),

and thus by (Equation 3) we can conclude that

\left|{\operatorname{supp}(\widetilde{w})}\right|\leq O\left(\mathrm{CL}(C)% \log^{2}(m)\log\log(m)^{2}/\epsilon^{2}\right),

as desired. $\hfill\blacktriangleleft$

[bib.bib1] [1] Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, Cambridge, 1999.

[bib.bib2] [2] Arpon Basu, Pravesh K. Kothari, Yang P. Liu, and Raghu Meka. Sparsifying sums of positive semidefinite matrices. In Kasper Green Larsen and Barna Saha, editors, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 6042–6064. SIAM, 2026. doi:10.1137/1.9781611978971.216.

[bib.bib3] [3] Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice-Ramanujan sparsifiers. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 255–262. ACM, 2009. doi:10.1145/1536414.1536451.

[bib.bib4] [4] András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Õ(n ${}^{\mbox{2}}$ ) time. In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 47–55. ACM, 1996. doi:10.1145/237814.237827.

[bib.bib5] [5] Christian Bessiere, Clément Carbonnel, and George Katsirelos. Chain Length and CSPs Learnable with Few Queries. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02):1420–1427, April 2020. doi:10.1609/aaai.v34i02.5499.

[bib.bib6] [6] Christian Bessiere, Remi Coletta, Emmanuel Hebrard, George Katsirelos, Nadjib Lazaar, Nina Narodytska, Claude-Guy Quimper, and Toby Walsh. Constraint acquisition via partial queries. In Francesca Rossi, editor, IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, pages 475–481. IJCAI/AAAI, 2013. URL: http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6659.

[bib.bib7] [7] Joshua Brakensiek and Venkatesan Guruswami. Redundancy is all you need. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 1614–1625. ACM, 2025. doi:10.1145/3717823.3718212.

[bib.bib8] [8] Silvia Butti and Stanislav Živný. Sparsification of Binary CSPs. SIAM Journal on Discrete Mathematics, 34(1):825–842, January 2020. doi:10.1137/19M1242446.

[bib.bib9] [9] Charles Carlson, Alexandra Kolla, Nikhil Srivastava, and Luca Trevisan. Optimal lower bounds for sketching graph cuts. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2565–2569. SIAM, 2019. doi:10.1137/1.9781611975482.158.

[bib.bib10] [10] Yu Chen, Sanjeev Khanna, and Ansh Nagda. Near-linear size hypergraph cut sparsifiers. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 61–72. IEEE, 2020. doi:10.1109/FOCS46700.2020.00015.

[bib.bib11] [11] Arnold Filtser and Robert Krauthgamer. Sparsification of two-variable valued constraint satisfaction problems. SIAM J. Discret. Math., 31(2):1263–1276, 2017. doi:10.1137/15M1046186.

[bib.bib12] [12] Wai Shing Fung, Ramesh Hariharan, Nicholas J.A. Harvey, and Debmalya Panigrahi. A general framework for graph sparsification. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, pages 71–80, New York, NY, USA, 2011. Association for Computing Machinery. doi:10.1145/1993636.1993647.

[bib.bib13] [13] Mohsen Ghaffari, David R. Karger, and Debmalya Panigrahi. Random contractions and sampling for hypergraph and hedge connectivity. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1101–1114. SIAM, 2017. doi:10.1137/1.9781611974782.71.

[bib.bib14] [14] Justin Gilmer. A constant lower bound for the union-closed sets conjecture. arXiv preprint, 2022. arXiv:2211.09055.

[bib.bib15] [15] Jun-Ting Hsieh, Daniel Z. Lee, Sidhanth Mohanty, Aaron Putterman, and Rachel Yun Zhang. Sparsifying cayley graphs on every group. In Kasper Green Larsen and Barna Saha, editors, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 6029–6041. SIAM, 2026. doi:10.1137/1.9781611978971.215.

[bib.bib16] [16] Arun Jambulapati, Yang P Liu, and Aaron Sidford. Chaining, group leverage score overestimates, and fast spectral hypergraph sparsification. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 196–206, 2023. doi:10.1145/3564246.3585136.

[bib.bib17] [17] Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida. Spectral hypergraph sparsifiers of nearly linear size. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1159–1170. IEEE, 2021. doi:10.1109/FOCS52979.2021.00114.

[bib.bib18] [18] Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida. Towards tight bounds for spectral sparsification of hypergraphs. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 598–611, 2021. doi:10.1145/3406325.3451061.

[bib.bib19] [19] David R. Karger. Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm. In Vijaya Ramachandran, editor, Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 25-27 January 1993, Austin, Texas, USA, pages 21–30. ACM/SIAM, 1993. URL: http://dl.acm.org/citation.cfm?id=313559.313605.

[bib.bib20] [20] Sanjeev Khanna, Aaron Putterman, and Madhu Sudan. Near-optimal size linear sketches for hypergraph cut sparsifiers. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1669–1706. IEEE, 2024. doi:10.1109/FOCS61266.2024.00105.

[bib.bib21] [21] Sanjeev Khanna, Aaron Putterman, and Madhu Sudan. Efficient algorithms and new characterizations for CSP sparsification. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 407–416. ACM, 2025. doi:10.1145/3717823.3718205.

[bib.bib22] [22] Sanjeev Khanna, Aaron Putterman, and Madhu Sudan. A theory of spectral CSP sparsification. arXiv preprint, 2025. doi:10.48550/arXiv.2504.16206.

[bib.bib23] [23] Sanjeev Khanna, Aaron (Louie) Putterman, and Madhu Sudan. Code sparsification and its applications. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 5145–5168. SIAM, 2024. doi:10.1137/1.9781611977912.185.

[bib.bib24] [24] Dmitry Kogan and Robert Krauthgamer. Sketching cuts in graphs and hypergraphs. In Tim Roughgarden, editor, Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 367–376. ACM, 2015. doi:10.1145/2688073.2688093.

[bib.bib25] [25] James R. Lee. Spectral hypergraph sparsification via chaining. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 207–218. ACM, 2023. doi:10.1145/3564246.3585165.

[bib.bib26] [26] Yi Li, Philip M. Long, and Aravind Srinivasan. Improved bounds on the sample complexity of learning. Journal of Computer and System Sciences, 62(3):516–527, 2001. doi:10.1006/jcss.2000.1741.

[bib.bib27] [27] Marcel K De Carli Silva, Nicholas JA Harvey, and Cristiane M Sato. Sparse sums of positive semidefinite matrices. ACM Transactions on Algorithms (TALG), 12(1):1–17, 2015. doi:10.1145/2746241.

[bib.bib28] [28] Tasuku Soma and Yuichi Yoshida. Spectral sparsification of hypergraphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2570–2581. SIAM, 2019. doi:10.1137/1.9781611975482.159.

[bib.bib29] [29] V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16:264–280, 1971.

	$\displaystyle\langle\widetilde{w},c\rangle$	$\displaystyle=\langle\widetilde{w}_{t-1},c\|_{I_{t-1}}\rangle+\langle\widetilde% {w}_{t},c\|_{I_{t}}\rangle+\sum_{t^{\prime}\leq t-2}\langle\widetilde{w}_{t^{% \prime}},c\|_{I_{t^{\prime}}}\rangle$
		$\displaystyle\in[1-\epsilon/2,1+\epsilon/2]\cdot\sum_{i\in I_{t-1}\cup I_{t}}w% (i)c_{i}+\sum_{t^{\prime}\leq t-2}\langle\widetilde{w}_{t^{\prime}},c\|_{I_{t^{% \prime}}}\rangle$
		$\displaystyle=[1-\epsilon/2,1+\epsilon/2]\cdot\left[\langle w,c\rangle-\sum_{i% \in\operatorname{supp}(c)\setminus(I_{t-1}\cup I_{t})}w(i)\right]+\sum_{t^{% \prime}\leq t-2}\langle\widetilde{w}_{t^{\prime}},c\|_{I_{t^{\prime}}}\rangle.$

Multiplicative Error Set System Sparsification: A Simpler Proof via Chain Length Contraction

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Acknowledgements:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1 (Theorem 1.4 of [7]).

1.1 Main Result

Theorem 2 (Main Result, see Theorem 22).

1.1.1 Improvement to Code Sparsification

1.2 Related Work

1.2.1 Code, CSP, and Cayley graph sparsification

1.2.2 Chain length and query complexity

1.2.3 Connections to Learning Theory

Organization

2 Preliminaries

2.1 Notation and Sparsification Definitions

Definition 3.

▶ Remark 4.

Definition 5.

Definition 6.

Claim 7.

2.2 Concentration Bound

Claim 8.

3 Chain Length Counting Bounds via Contractions

Lemma 9.

3.1 Contractions

Claim 10.

Proof.

3.2 Contraction Algorithm

Definition 11.

Claim 12.

Proof.

Claim 13.

Proof.

Lemma 14.

Proof.

4 Leveraging Decomposition to Build Sparsifiers

4.1 Basic Sparsifier Construction for Unweighted Codes

Theorem 15.

Claim 16.

Proof.

Claim 17.

Proof.

Claim 18.

Proof.

Claim 19.

Proof.

Theorem 20.

Proof.

Corollary 21.

4.2 Dimension-Free Bounds

Theorem 22.

Proof.

5 Conclusion

Truly linear sparsifiers.

Conjecture 23.

References

Appendix A Proof of Corollary 21

Corollary 24.

Proof.

Proof of Corollary 21.

Multiplicative Error Set System Sparsification:
A Simpler Proof via Chain Length Contraction

$\blacktriangleright$ Remark 4.