技术摘要：冗余即所需（针对 CSP 稀疏化）

问题陈述

本文解决了约束满足问题（CSP）稀疏化的问题。其目标是用一个显著更小的加权子实例替换大型 CSP 实例，使得该子实例在 $(1 \pm \epsilon)$ 的乘积因子范围内，保留每一个可能赋值所满足的约束数量（即价值）。

虽然稀疏化在图割（Bencz´ur 和 Karger）和线性码（Khanna, Putterman, Sudan）等特定案例中已得到充分理解，但针对任意 CSP 谓词的一般情况此前仍是一个未解之谜。任何稀疏化器大小的平凡下界是实例的非冗余性：即最大约束子集的大小，其中每个约束都由某个赋值唯一满足，而该赋值不满足子集中的任何其他约束。如果一个实例是非冗余的，则无法在不改变某些赋值价值的情况下丢弃任何约束。Kogan 和 Krauthgamer 提出的核心问题是：这个平凡下界是否对所有 CSP 都基本上是紧确的，或者是否存在需要显著更大稀疏化器的谓词。

方法论

作者将 CSP 稀疏化的研究与非线性码稀疏化的研究统一起来。他们将 CSP 实例建模为一组码字（赋值的指示向量），并寻求一个稀疏权重向量，以近似每个码字的汉明重量。

核心技术创新包含两个主要支柱：

1. 熵方法与并闭集：
   作者调整了 Gilmer 近期为证明并闭集猜想（在常数因子范围内）而开发的熵方法。在稀疏化的背景下，他们利用该方法来界定码的"OR-闭包”的大小。

   • 他们建立了一个二分法：对于任何码，要么存在一个码上的分布，其坐标是“稀疏的”（取值为 1 的可能性低），要么存在一个坐标上的分布，能够“覆盖”每一个码字。
   • 在“稀疏”情况下，他们利用 Sawin 改进的 Gilmer 熵界，证明码的大小在其非冗余性上是拟多项式的，从而允许进行高效的子采样。
   • 在“覆盖”情况下，他们迭代地选择坐标以纳入稀疏化器中。
   • 这种方法取代了用于线性码的“分治”策略，转而采用对非线性码的稠密和稀疏结构进行更细致的分析。

2. 匹配向量族：
   为了分析那些“接近”线性但并非完全线性的特定谓词（具体指 $3\text{LIN}^*_G$，即群 $G$ 上 $x+y+z=0$ 的非零解集），作者将非冗余性问题与局部可解码码（LDCs）中使用的匹配向量（MV）族联系起来。

   • 他们引入了条件非冗余性并定义了$G$-系综，这将匹配向量族推广到了向量三元组。
   • 通过调整 Dvir、Gopalan 和 Yekhanin 的技术，他们推导出了这些系综大小的非平凡上下界，进而得出了特定谓词非冗余性的界限。

主要贡献与结果

1. 无权重 CSP 的最优稀疏化界限

本文确立了谓词 $R$ 的非冗余性（记为 $\text{NRD}(R, n)$）精确刻画了由 $R$ 定义的 CSP 的稀疏化能力。

• 定理 1.1（码稀疏化）： 对于任何非线性码 $C \subseteq \{0,1\}^m$，$\epsilon$-稀疏化器的大小受限于 $O(\text{NRD}(C) (\log m)^6 / \epsilon^2)$。
• 定理 1.2（CSP 稀疏化）： 对于任何 CSP 谓词 $R$，其稀疏化能力 $\text{SPR}(R, n, \epsilon)$ 满足：
  $$\text{NRD}(R, n) \leq \text{SPR}(R, n, \epsilon) \leq O(\text{NRD}(R, n) (r \log n)^6 / \epsilon^2)$$
  该结果证实，冗余子句足以进行稀疏化；可以将任何实例稀疏化到与其非冗余性成比例的大小（最多相差多项式对数因子）。

2. 加权稀疏化与链长

对于加权实例，作者确定了链长（$\text{CL}$）作为支配参数。

• 定理 1.3 / 5.4： 加权稀疏化能力被码/谓词的链长紧密界定：
  $$\text{CL}(C) \leq \text{wSPR}(C, \epsilon) \leq O(\text{CL}(C) (\log m)^6 / \epsilon^2)$$
  链长定义为对角线上为 1 的最大上三角子矩阵的维数。本文表明 $\text{NRD}(C) \leq \text{CL}(C)$，且对于加权实例，链长可以严格更大。

3. 通过匹配向量获得的非冗余性新界限

作者提供了具有非整数指数非冗余性的谓词的首个示例。

• 定理 1.4： 对于谓词 $3\text{LIN}^*_{\mathbb{Z}/3\mathbb{Z}}$（$\mathbb{Z}_3$ 上 $x+y+z=0$ 的非零解）：
  $$\text{NRD}(3\text{LIN}^*_{\mathbb{Z}/3\mathbb{Z}}, n) \in [\Omega(n^{1.5}), \tilde{O}(n^{1.6})]$$
  这是通过使用 $G$-系综构造大小为 $\Omega(n^{1.5})$ 的非冗余实例，并利用多项式方法和向量空间维度的组合归纳法证明 $\tilde{O}(n^{1.6})$ 的上界来实现的。

4. 直接应用

通过将稀疏化与非冗余性联系起来，本文立即将已知结果扩展到了新领域：

• 非阿贝尔群： 对于任何有限群（阿贝尔或非阿贝尔）上的码，存在大小为 $O(\log |H| (\log m)^6 / \epsilon^2)$ 的稀疏化器。
• Mal'tsev 谓词： 这些谓词（推广了仿射约束）具有线性非冗余性，意味着具有近线性的稀疏化能力。
• 最大规模二分法： 本文恢复了二分法结论：谓词要么具有近线性稀疏化器，要么需要 $\Omega(n^r)$ 的大小，这取决于它们是否包含特定硬约束的特定“诱导副本”。

意义

本文声称精确确定了任何 CSP 可被稀疏化的程度。通过证明平凡下界（非冗余性）基本上是紧确的，它解决了关于任意 CSP 稀疏化能力的十年之久的疑问。

• 统一性： 它将割稀疏化器、线性码稀疏化器和一般 CSP 稀疏化的理论统一在非线性码稀疏化的单一框架之下。
• 新颖技术： 将 Gilmer 的熵方法应用于稀疏化被视为一项突破，使得处理先前线性代数技术失效的非线性结构成为可能。
• 新的组合洞察： 与匹配向量族的联系为分析 CSP 谓词的复杂性提供了新视角，产生了首个已知的非整数非冗余性指数示例。

作者指出，虽然他们的结果是存在性的（证明了稀疏化器的存在），但使构造变得高效（即 $n$ 的多项式时间）仍然是一个未解决的挑战，因为这等价于将 CSP 高效地核化为其非冗余性的开放问题。