New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs

1. 問題設定 (Problem)

制約充足問題 (CSP) は、変数の割り当てが与えられた制約（述語）をどれだけ満たすかを扱う問題です。近年、より一般的な PCSP が研究されており、これは「強い制約 $P$ を満たす割り当てが存在すると約束されている場合に、弱い制約 $Q$ を満たす割り当てを見つける」という問題です。

本論文が焦点を当てる ロバスト充足可能性 とは、以下の性質を持つアルゴリズムを指します：

• 入力: 制約の $(1-\epsilon)$ 割合が強い制約 $P$ を満たす（almost-satisfiable）インスタンス。
• 出力: 制約の $(1-g(\epsilon))$ 割合が弱い制約 $Q$ を満たす割り当て。
• ここで、$g(\epsilon)$ は $\epsilon \to 0$ のとき $0$ に収束する損失関数です。

従来の CSP では、多項式時間で解ける問題（tractable）とそうでない問題の境界（Dichotomy Theorem）が判明していますが、PCSP においては「どの程度のロバストな損失 $g(\epsilon)$ が許容されるか」という定量的側面は未解明な部分が多く残されています。

2. 手法 (Methodology)

論文では、主に以下の3つの数学的手法を用いています。

1. 半正定値計画法 (SDP) と丸め (Rounding):
   SDP を用いて変数をベクトルとして表現し、ガウス分布を用いたランダムな丸め（CMM アルゴリズムの拡張）や、多変量正規分布の解析を用いて、連続的なベクトル解から離散的な割り当てを生成します。
2. ポリモーフィズム (Polymorphisms) の代数的解析:
   制約集合の構造を決定する代数的演算子（Majority, Alternating Threshold, Plurality など）の性質を利用して、アルゴリズムの成功確率を解析します。
3. 積分ギャップ (Integrality Gap) の構築:
   Unique Games Conjecture (UGC) の下で、SDP の解は高い値を示すが、実際の割り当てでは多くの制約が破れるような「最悪のケース」のインスタンスを、高次元のガウス分布や離散化技術を用いて構築します。

3. 主要な貢献と結果 (Key Contributions and Results)

論文の貢献は大きく3つの柱に分かれます。

① Alternating Threshold (AT) 多項式の困難性証明

先行研究 [BGS25] では、AT 多項式を持つ PCSP がロバストであることが示されていましたが、その損失 $g(\epsilon)$ は指数的な損失（$\log \log(1/\epsilon) / \log(1/\epsilon)$）でした。

• 結果: 本論文は、UGC を仮定すると、1-in-3-SAT vs NAE-SAT という特定の PCSP において、損失が $1/\log(1/\epsilon)$ を下回ることは困難であることを証明しました。
• 意義: これにより、AT 多項式における指数的な損失が、アルゴリズムの限界ではなく、問題の本質的な困難さ（必要性）であることが示されました。

② Majority および Plurality 多項式のアルゴリズム改善

Majority (MAJ) 多項式を持つ Boolean PCSP に対するロバストアルゴリズムの解析を大幅に改善しました。

• 結果:
  • Majority: 損失を $O(\epsilon^{1/3})$ から $O(\sqrt{\epsilon})$ へ改善。これは 2-SAT における最適値と一致し、UGC 下でタイトです。
  • Plurality / Separable Families: 非 Boolean ドメイン（より大きな値域）においても、$O(\sqrt{\epsilon} \log(1/\epsilon))$ という非常に小さな損失で解けることを示しました。
• 意義: 多くの重要な PCSP（Unique Games や SetSAT など）がこの範疇に含まれ、それらのロバスト性を理論的に保証しました。

③ 等価制約 (Equality Constraints) によるロバスト性の保存

既存の PCSP 理論において、等価制約 ($x=y$) を追加した際にロバスト性がどのように変化するかは不明でした。

• 結果: UGC の下で、ある PCSP がロバストであれば、等価制約を追加した PCSP も（多項式的な損失の範囲内で）ロバストであることを証明しました。
• 手法: Brown-Cohen および Raghavendra のアルゴリズムを拡張し、「相関丸め (Correlated Rounding)」 と 「$\delta$-smoothing」 という新しい技術を導入しました。
• 意義: これにより、既存の強力なガジェット還元（Gadget Reductions）の手法を、ロバストな PCSP の研究にそのまま適用できるようになりました。

4. 論文の意義 (Significance)

本論文は、PCSP の複雑性理論における「定量的ロバスト性」の理解を一段階引き上げました。

1. 理論的境界の明確化: 多項式的な損失が得られるケース（Majority/Plurality）と、指数的な損失が避けられないケース（AT）を明確に区別しました。
2. アルゴリズムの一般化: 2-SAT などの古典的な結果を、より広範な代数的構造（Separable PCSPs）へと一般化しました。
3. 研究ツールの提供: 等価制約の保存に関する結果は、今後の PCSP 分類学において、ガジェットを用いた還元を容易にする強力な基盤となります。

総じて、本論文は代数、幾何、確率論を高度に融合させ、近似アルゴリズムと計算複雑性理論の境界線をより精密に描き出した重要な研究です。