Description
Constraint Satisfaction Problems (CSPs) provide a unifying framework for capturing a wide array of computational problems. A basic notion in this landscape is that of redundancy: a constraint is redundant if it is logically implied by the rest. The study of
non-redundancy—instances where no constraint is redundant—has recently emerged as a surprisingly powerful lens for understanding core questions in sparsification, kernelization, extremal combinatorics, and universal algebra.
In this talk, I will describe a recent line of work that systematically develops the theory of CSP non-redundancy. A central
result (with J. Brakensiek, STOC 2025) shows that the sparsifiability of any CSP is determined—up to polylogarithmic factors—by its non-redundancy. This unifies and significantly extends known sparsification results for graph cuts, linear codes, and various CSP classes. The proof involves a novel application of the entropy method, inspired by Gilmer’s recent breakthrough on the union-closed sets conjecture.
In follow-up work (with J. Brakensiek, B. Jansen, V. Lagerkvist, and M. Wahlström), we construct explicit CSP predicates whose
non-redundancy scales as Θ(n^r) for every rational r ≥ 1, revealing a rich and previously unanticipated spectrum. We also develop an algebraic theory of conditional non-redundancy via pattern polymorphisms, drawing connections to Turán-type extremal problems in graphs and hypergraphs. Further extending this theory, we revisit the notion of Mal’tsev embeddings—the most general known technique for proving linear non-redundancy. Introducing a new tool, Catalan polymorphisms, we resolve several structural questions about Mal’tsev embeddings, including the construction of a predicate whose embedding arises not from an Abelian group, but from the quantum Pauli group.
This work illustrates how the seemingly modest notion of redundancy unfolds into a deep and multifaceted theory, bridging ideas from combinatorics, algebra, logic, and theoretical computer science.