An instance of a constraint satisfaction problem is called non-redundant if no constraint is implied by the rest; that is, for each constraint, there exists an assignment that violates that constraint while satisfying all others. The non-redundancy (NRD) of a relation R is the maximum number of constraints in a non-redundant CSP instance over R, as a function of the number n of variables. In recent work, we showed that the extent to which a CSP can be sparsified is determined—up to polylogarithmic factors—by the NRD of its associated relation. More broadly, non-redundancy lies at an interesting nexus of logic, extremal combinatorics, and algebra, motivating its detailed study.
In this talk, I will report several results that illuminate the rich landscape of NRD. The NRD of an arity-r relation over a finite domain lies between n and n^r, and when r=2, exhibits a sharp linear-versus-quadratic dichotomy. Prior to recent work, all known examples were consistent with NRD exhibiting only polynomial growth n^c for integer exponents c. We show that the behavior of NRD is substantially richer. In particular, we prove that a simple relation over {0,1,2}^3 has NRD between n^{1.5} and n^{1.6}, and that for every rational s \ge 1, there exists a relation with NRD = \Theta(n^s). Using connections to high-girth constructions in extremal combinatorics, we further show that infinitely many exponents arise as the NRD of relations even for arity 3.
We also revisit Mal’tsev embeddings, the most general sufficient condition currently known for O(n) NRD, and resolve several structural questions about them, using a new tool called Catalan polymorphisms. In particular, we give the first example of a relation that admits no Abelian embedding but does embed into the non-Abelian quantum Pauli group.
Based on joint work with Josh Brakensiek (STOC 2025), and with Josh Brakensiek, Bart Jansen, Victor Lagerkvist, and Magnus Wahlström (arXiv:2507.07942).