🔢 mathematics

Redundancy Is All You Need (for CSP Sparsification)

This paper establishes that any constraint satisfaction problem (CSP) instance can be sparsified to a size proportional to its non-redundancy (or chain length for weighted cases) by proving that redundant clauses are sufficient for approximation, a result achieved through novel applications of the entropy method and coding theory techniques that precisely determine the limits of CSP sparsification.

Original authors: Joshua Brakensiek, Venkatesan Guruswami

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Joshua Brakensiek, Venkatesan Guruswami

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, messy library of rules. Each rule is a constraint, like "If you wear a red hat, you must wear blue shoes" or "If you eat an apple, you cannot eat a banana." In computer science, this is called a Constraint Satisfaction Problem (CSP).

Now, imagine you want to check if a specific set of choices (an "assignment") satisfies these rules. If you have millions of rules, checking them all is slow and expensive. Sparsification is the art of throwing away most of the rules while keeping just enough so that the "score" of any set of choices remains exactly the same (within a tiny margin of error). It's like trying to describe a 10,000-page novel using only a few key sentences that still capture the entire plot.

For decades, researchers knew how to do this for simple cases, like graph cuts (splitting a network in two). But for complex, arbitrary rules, they were stuck. They knew you couldn't throw away a rule if that rule was the only thing stopping a specific scenario from happening. But they didn't know how much "extra" (redundant) information was actually needed to keep the system working.

This paper, "Redundancy Is All You Need," by Joshua Brakensiek and Venkatesan Guruswami, solves this mystery. Here is the breakdown in simple terms:

1. The Core Discovery: "Redundancy is the Limit"

The authors discovered that the size of the smallest possible "summary" (sparsifier) of your rulebook is determined entirely by how many unique, non-redundant rules you have.

The Analogy: Imagine a team of 1,000 people trying to solve a puzzle.
- Redundant Rules: These are like having 900 people who all say the exact same thing. You can fire 899 of them, and the team still works.
- Non-Redundant Rules: These are the 100 people who each hold a unique, critical piece of information. If you fire any one of them, the team fails a specific test.
The Result: The paper proves that you can compress your entire rulebook down to a size roughly equal to the number of these "unique, critical" people (plus a tiny bit of extra space for safety). You don't need to keep the redundant 900 people.

2. The "Entropy" Magic Trick

How did they prove this? They used a mathematical tool called Entropy, borrowed from a recent breakthrough in a completely different field (the "Union-Closed Sets Conjecture").

The Metaphor: Imagine you are trying to identify a specific person in a crowd by asking yes/no questions.
- If the crowd is very diverse (high entropy), you need many questions to find them.
- If the crowd is very similar (low entropy), you need fewer questions.
The authors used this concept to show that even if your rulebook looks chaotic, the "information density" of the unique rules is low enough that you can pick a small, random sample of rules that still represents the whole crowd perfectly. They didn't just guess; they proved that a specific mathematical "temperature" (entropy) guarantees this compression works.

3. Weighted Rules (The "Heavy" Constraints)

Sometimes, rules aren't just "on" or "off"; they have weights (importance). Maybe one rule is worth 10 points and another is worth 1.

The paper introduces a new concept called Chain Length.
The Analogy: Imagine a staircase. You can't skip a step. If you have a chain of rules where Rule A implies Rule B, which implies Rule C, you can't throw away the middle ones without breaking the chain.
The authors show that for weighted rules, the size of your summary depends on the length of the longest such "staircase" of dependencies in your rules.

4. The "First of Its Kind" Discovery

The paper also looked at specific types of rules (like those involving adding numbers in a circle, e.g., modulo arithmetic).

They found a specific set of rules where the number of necessary rules grows at a rate that is not a whole number.
The Metaphor: Usually, things grow in whole steps (like $n^2$ or $n^3$ ). This paper found a rulebook that grows like $n^{1.5}$ (one and a half). It's the first time anyone has proven that a rulebook's complexity can sit "between" whole number steps.

5. What This Means (According to the Paper)

For Computer Scientists: It provides a universal formula. If you want to know how small you can make a CSP problem, you just need to count its "non-redundancy" (for simple rules) or "chain length" (for weighted rules).
For the Field: It unifies many different areas (graph theory, coding theory, and logic) under one single mathematical roof.
The Caveat: The paper proves that such a small summary exists. It doesn't necessarily give a fast, easy algorithm to find it for every single case (that remains a hard open question for the future).

In Summary:
The paper says, "Stop trying to keep every single rule. If you identify the 'unique' rules that no other rule can replace, you can throw away everything else. The size of your new, tiny rulebook will be exactly the size of those unique rules." They proved this using a clever math trick involving information theory and entropy, solving a decade-old question about how much we can compress complex logical systems.

Technical Summary: Redundancy Is All You Need (for CSP Sparsification)

Problem Statement

The paper addresses the problem of Constraint Satisfaction Problem (CSP) sparsification. The goal is to replace a large CSP instance with a significantly smaller, weighted sub-instance that preserves the value (number of satisfied constraints) of every possible assignment to within a multiplicative factor of $(1 \pm \epsilon)$ .

While sparsification is well-understood for specific cases like graph cuts (Bencz´ur and Karger) and linear codes (Khanna, Putterman, Sudan), the general case for arbitrary CSP predicates remained open. A trivial lower bound for the size of any sparsifier is the non-redundancy of the instance: the size of the largest subset of constraints where each constraint is uniquely satisfied by some assignment that satisfies no other constraint in the subset. If an instance is non-redundant, no constraint can be dropped without altering the value of some assignment. The central question posed by Kogan and Krauthgamer is whether this trivial lower bound is essentially tight for all CSPs, or if there exist predicates requiring significantly larger sparsifiers.

Methodology

The authors unify the study of CSP sparsification with non-linear code sparsification. They model a CSP instance as a set of codewords (indicator vectors of assignments) and seek a sparse weight vector that approximates the Hamming weight of every codeword.

The core technical innovation involves two main pillars:

Entropy Method and Union-Closed Sets:
The authors adapt the entropy method recently developed by Gilmer to prove the Union-Closed Sets Conjecture (up to a constant factor). In the context of sparsification, they utilize this method to bound the size of the "OR-closure" of a code.
- They establish a dichotomy: for any code, either there exists a distribution over the code where coordinates are "sparse" (unlikely to be 1), or there exists a distribution over coordinates that "covers" every codeword.
- In the "sparse" case, they use Gilmer's entropy bounds (refined by Sawin) to show that the code's size is quasipolynomial in its non-redundancy, allowing for efficient subsampling.
- In the "covering" case, they iteratively select coordinates to include in the sparsifier.
- This approach replaces the "divide-and-conquer" strategies used for linear codes with a more nuanced analysis of the dense and sparse structures of non-linear codes.
Matching Vector Families:
To analyze specific predicates that are "close" to linear but not quite (specifically $3\text{LIN}^*_G$ , the set of non-zero solutions to $x+y+z=0$ over a group $G$ ), the authors connect the non-redundancy problem to Matching Vector (MV) families used in Locally Decodable Codes (LDCs).
- They introduce conditional non-redundancy and define $G$ -ensembles, which generalize MV families to triples of vectors.
- By adapting techniques from Dvir, Gopalan, and Yekhanin, they derive non-trivial upper and lower bounds on the size of these ensembles, leading to bounds on the non-redundancy of specific predicates.

Key Contributions and Results

1. Optimal Sparsification Bounds for Unweighted CSPs

The paper establishes that the non-redundancy of a predicate $R$ , denoted $\text{NRD}(R, n)$ , precisely characterizes the sparsifiability of CSPs defined by $R$ .

Theorem 1.1 (Code Sparsification): For any non-linear code $C \subseteq \{0,1\}^m$ , the size of an $\epsilon$ -sparsifier is bounded by $O(\text{NRD}(C) (\log m)^6 / \epsilon^2)$ .
Theorem 1.2 (CSP Sparsification): For any CSP predicate $R$ , the sparsifiability $\text{SPR}(R, n, \epsilon)$ satisfies:
$\text{NRD}(R, n) \leq \text{SPR}(R, n, \epsilon) \leq O(\text{NRD}(R, n) (r \log n)^6 / \epsilon^2)$
This result confirms that redundant clauses are sufficient for sparsification; one can sparsify any instance down to a size proportional to its non-redundancy (up to polylogarithmic factors).

2. Weighted Sparsification and Chain Length

For weighted instances, the authors identify Chain Length ( $\text{CL}$ ) as the governing parameter.

Theorem 1.3 / 5.4: The weighted sparsifiability is tightly bounded by the chain length of the code/predicate:
$\text{CL}(C) \leq \text{wSPR}(C, \epsilon) \leq O(\text{CL}(C) (\log m)^6 / \epsilon^2)$
Chain length is defined as the dimension of the largest upper-triangular submatrix with 1s on the diagonal. The paper shows $\text{NRD}(C) \leq \text{CL}(C)$ , and for weighted instances, the chain length can be strictly larger.

3. New Bounds on Non-Redundancy via Matching Vectors

The authors provide the first examples of predicates with non-integral exponents for non-redundancy.

Theorem 1.4: For the predicate $3\text{LIN}^*_{\mathbb{Z}/3\mathbb{Z}}$ (non-zero solutions to $x+y+z=0$ over $\mathbb{Z}_3$ ):
$\text{NRD}(3\text{LIN}^*_{\mathbb{Z}/3\mathbb{Z}}, n) \in [\Omega(n^{1.5}), \tilde{O}(n^{1.6})]$
This is achieved by constructing a non-redundant instance of size $\Omega(n^{1.5})$ using a $G$ -ensemble and proving an upper bound of $\tilde{O}(n^{1.6})$ using polynomial methods and combinatorial induction on the vector space dimension.

4. Immediate Applications

By linking sparsification to non-redundancy, the paper immediately extends known results to new domains:

Non-Abelian Groups: Sparsifiers of size $O(\log |H| (\log m)^6 / \epsilon^2)$ exist for codes over any finite group (Abelian or non-Abelian).
Mal'tsev Predicates: These predicates (generalizing affine constraints) have linear non-redundancy, implying near-linear sparsifiability.
Maximum-Size Dichotomy: The paper recovers the dichotomy that predicates either have near-linear sparsifiers or require $\Omega(n^r)$ size, depending on whether they contain a specific "induced copy" of a hard constraint.

Significance

The paper claims to precisely determine the extent to which any CSP can be sparsified. By proving that the trivial lower bound (non-redundancy) is essentially tight, it resolves a decade-old question regarding the sparsifiability of arbitrary CSPs.

Unification: It unifies the theory of cut sparsifiers, linear code sparsifiers, and general CSP sparsification under a single framework of non-linear code sparsification.
Novel Techniques: The application of Gilmer's entropy method to sparsification is presented as a breakthrough, allowing for the handling of non-linear structures where previous linear-algebraic techniques failed.
New Combinatorial Insights: The connection to Matching Vector families provides a new lens for analyzing the complexity of CSP predicates, yielding the first known examples of non-integral non-redundancy exponents.

The authors note that while their results are existential (proving the existence of sparsifiers), making the construction efficient (polynomial time in $n$ ) remains an open challenge, as it is equivalent to the open problem of efficiently kernelizing CSPs to their non-redundancy.