标题： CSP非冗余性的重要性 显示英文标题

标题： The Richness of CSP Non-redundancy

摘要： 在约束满足问题（CSP）领域，如果一个子句的满足由满足所有其他子句所隐含，则该子句被称为冗余的。 CSP$(P)$的一个实例被称为非冗余的，如果它不包含任何冗余子句。 谓词$P$的非冗余性（NRD）是作为变量数量$n$的函数，在CSP$(P)$的非冗余实例中子句的最大数量。 最近的研究进展表明，非冗余性与计算机科学和数学中的许多其他重要问题密切相关，包括稀疏化、核化、查询复杂性、通用代数和极值组合学。 鉴于非冗余性是这些重要问题的一个交汇点，本文的核心目标是更深入地理解非冗余性。 我们第一个主要结果表明，对于每个有理数$r \ge 1$，存在一个有限的CSP谓词$P$，使得$P$的非冗余性为$\Theta(n^r)$。 我们的第二个主要结果探讨了由Brakensiek和Guruswami [STOC 2025]首次提出的条件非冗余性概念。 我们通过将这些非冗余性问题与极值组合学中高环长图的结构相联系，对所有二元谓词（即对两个变量的约束）的条件非冗余性进行了完全分类。 受这些具体结果的启发，我们基于Carbonnel [CP 2022]的工作，发展了一个条件非冗余性的代数理论。 作为该代数理论的应用，我们重新审视了Mal'tsev嵌入的概念，这是目前用于证明一个谓词具有线性非冗余性的最一般技术。 例如，我们提供了第一个具有Mal'tsev嵌入的谓词示例，该示例不能归因于阿贝尔群的结构，而是归因于量子泡利群的结构。 显示英文摘要

摘要： In the field of constraint satisfaction problems (CSP), a clause is called redundant if its satisfaction is implied by satisfying all other clauses. An instance of CSP$(P)$ is called non-redundant if it does not contain any redundant clause. The non-redundancy (NRD) of a predicate $P$ is the maximum number of clauses in a non-redundant instance of CSP$(P)$, as a function of the number of variables $n$. Recent progress has shown that non-redundancy is crucially linked to many other important questions in computer science and mathematics including sparsification, kernelization, query complexity, universal algebra, and extremal combinatorics. Given that non-redundancy is a nexus for many of these important problems, the central goal of this paper is to more deeply understand non-redundancy. Our first main result shows that for every rational number $r \ge 1$, there exists a finite CSP predicate $P$ such that the non-redundancy of $P$ is $\Theta(n^r)$. Our second main result explores the concept of conditional non-redundancy first coined by Brakensiek and Guruswami [STOC 2025]. We completely classify the conditional non-redundancy of all binary predicates (i.e., constraints on two variables) by connecting these non-redundancy problems to the structure of high-girth graphs in extremal combinatorics. Inspired by these concrete results, we build off the work of Carbonnel [CP 2022] to develop an algebraic theory of conditional non-redundancy. As an application of this algebraic theory, we revisit the notion of Mal'tsev embeddings, which is the most general technique known to date for establishing that a predicate has linear non-redundancy. For example, we provide the first example of predicate with a Mal'tsev embedding that cannot be attributed to the structure of an Abelian group, but rather to the structure of the quantum Pauli group.