The replica symmetric phase of random constraint satisfaction problems
The replica symmetric phase of random constraint satisfaction problems
复制标题
DOI：
10.1017/s0963548319000440
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
A. Coja-Oghlan;Tobias Kapetanopoulos;Noëla Müller
中科院分区：
文献类型：
--
作者：
A. Coja-Oghlan;Tobias Kapetanopoulos;Noëla Müller
随机约束满足问题在计算机科学和组合数学中占有重要地位。例如，它们为算法提供了具有挑战性的基准示例，并且它们已被利用在具有特殊特征的组合结构的概率构造中。在一项重要贡献（Krzakala等人，2007，Proc.Nat.Acad. Sci.），物理学家对随机约束满足问题中相变的精确位置和性质做出了几个预测。具体来说，他们预测，他们的可满足性阈值通常在几个其他阈值之前，这些阈值在组合和计算方面都有很大的影响。这些包括凝结相变，变量之间的长程相关性出现，和重建阈值。在本文中，我们证明了这些物理预测广泛的一类随机约束满足问题。此外，我们还获得了对贝叶斯推理任务有影响的邻近结果，这是一个最近引起广泛兴趣的主题（例如Banks et al. 2016，Proc. 29th COLT）。
Abstarct Random constraint satisfaction problems play an important role in computer science and combinatorics. For example, they provide challenging benchmark examples for algorithms, and they have been harnessed in probabilistic constructions of combinatorial structures with peculiar features. In an important contribution (Krzakala et al. 2007, Proc. Nat. Acad. Sci.), physicists made several predictions on the precise location and nature of phase transitions in random constraint satisfaction problems. Specifically, they predicted that their satisfiability thresholds are quite generally preceded by several other thresholds that have a substantial impact both combinatorially and computationally. These include the condensation phase transition, where long-range correlations between variables emerge, and the reconstruction threshold. In this paper we prove these physics predictions for a broad class of random constraint satisfaction problems. Additionally, we obtain contiguity results that have implications for Bayesian inference tasks, a subject that has received a great deal of interest recently (e.g. Banks et al. 2016, Proc. 29th COLT).