Redundancy is all you need (for CSP sparsification)

Constraint Satisfaction Problems (CSPs) form a broad and central class in the theory of computation. I will describe a recent result (with J. Brakensiek, STOC ’25) showing that every CSP admits a sparsifier whose size is within polylogarithmic factors of its maximum non-redundant instance, while preserving the value of every assignment up to a small multiplicative error. A non-redundant instance is one where every constraint is essential, in the sense that some assignment satisfies exactly that constraint and no others—making such instances natural lower bounds for sparsification (for example, spanning trees are the non-redundant cut instances in graphs).

Our result is established in the general setting of set families, yielding a VC-type theorem for multiplicative approximation. This unifies and extends known sparsification results for graph cuts, linear codes, and broad CSP classes. The proof hinges on an elegant entropic inequality underlying Gilmer's recent breakthrough on the union-closed sets conjecture. 

As a consequence of our main theorem, several results from the non-redundancy (NRD) literature immediately extend to CSP sparsification. We also obtain new results that illuminate the rich landscape of NRD itself: in recent work with Brakensiek, Jansen, Lagerkvist, and Wahlström, we show that for every rational r > 1 there exists a CSP with NRD growing as Theta(n^r). We develop an algebraic theory of conditional NRD via pattern polymorphisms, linking NRD—and hence sparsification—to Turán-type extremal problems. Revisiting Mal’tsev embeddings, the most general known route to O(n) NRD, we introduce Catalan polymorphisms, resolving several structural questions about Mal’tsev embeddings, including a predicate that admits no Abelian embedding but does embed into the non-Abelian quantum Pauli group.