paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Smooth approximations and CSPs over finitely bounded homogeneous structures

光滑逼近与有限有界齐次结构上的 CSP
LICS Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science2022匹配度 1/10 · 该论文是有限模型论与约束满足问题（CSP）复杂性的纯理论研究，关注光滑逼近技术和齐次结构上的 CSP 二分类，不涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析，与用户研究画像的核心方向基本无关。引用 31 inbox
Antoine Mottet, Michael Pinsker
逻辑与自动机逻辑与约束编程
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话：提出光滑逼近技术，统一证明随机锦标赛等齐次结构上 CSP 的二分类，并刻画局部一致性可解性。

本文研究有限有界齐次结构上一阶归约的约束满足问题（CSP）的复杂度二分类与局部一致性可解性。作者引入“光滑逼近”这一新证明机制，用于获得 CSP 二分类结果并统一已有证明。借助该机制，作者确认了随机锦标赛的一阶归约的 CSP 二分类猜想，并为随机图等齐次图以及有理数序的扩张给出更短的新证明，同时显著简化已有文献结果。除最后一类结构外，还首次刻画了可由局部一致性方法求解的 CSP。评估为纯理论证明，未涉及实验。

问题
确定有限有界齐次结构（如随机锦标赛的一阶归约、齐次图、有理数序扩张）上 CSP 的复杂度二分类，并识别局部一致性可解的 CSP。
方法
引入光滑逼近（smooth approximations）这一新证明机制，用于 CSP 二分类证明与局部一致性刻画。
评估
以理论证明形式验证：确认随机锦标赛一阶归约的 CSP 二分类猜想，为随机图等齐次图和有理数序扩张给出更短证明，并统一简化已有结果。
原文摘要（Abstract）

We introduce the novel machinery of smooth approximations, and apply it to confirm the CSP dichotomy conjecture for first-order reducts of the random tournament, and to give new short proofs of the conjecture for various homogeneous graphs including the random graph (STOC’11, ICALP’16), and for expansions of the order of the rationals (STOC’08). Apart from obtaining these dichotomy results, we show how our new proof technique allows to unify and significantly simplify the previous results from the literature. For all but the last structure, we moreover characterize for the first time those CSPs which are solvable by local consistency methods, again using the same machinery.

链接与引用

DOI 原文 · arXiv · PDF（开放获取） · DBLP

BibTeX 
@inproceedings{abs-2011-03978,
  title = {Smooth approximations and CSPs over finitely bounded homogeneous structures},
  author = {Antoine Mottet and Michael Pinsker},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3533353}
}