该论文研究了随机约束满足问题的解空间结构，并证明了在解消失之前，它们会组成指数数量的簇，并且每个簇都相对较小且相距较远。此外，每个簇内的大部分变量都被冻结，并提出 Survey Propagation 算法的一项重要假设。

Nov, 2006

我们利用统计物理学中的一步副本对称性预测，为所有的 k≥k_0，建立了随机 k-SAT 的可满足性阈值，给出满足阈值和不满足阈值的限制密度的显式计算公式，并用一种新的分析方法对随机图进行矩计算，将一个高维的优化问题映射到了一个更易处理的分析树递归问题，证明了我们的阈值计算方法适用于 1-RSB 普适性类中的各种随机约束满足问题。

Nov, 2014

该论文研究了具有共同概率分布的独立随机点构成的随机几何图中色数和团数的关系，并确定了色数相对于团数的渐近比例，同时发现了一个尖锐的阈值。

Jan, 2011

这篇研究报告讨论了如何解决 NP-Complete 决策问题中的 “相位边界” 问题，介绍了在 K-SAT 中发生的相变的解析解和实验研究。其中，在计算代价随问题规模呈指数级增长的情况下，首次发现了 “随机一阶相变” 的本质，并提出了可能的搜索启发式算法改进方案来应对决策问题中的 “脊骨”。

Oct, 1999

研究了随机约束满足性问题的两个典型集合，并主要考虑其相空间的纯态、相变等问题，阐述了相变精确位置和多种算法在不同相的表现，包括局部蒙特卡罗马尔科夫链、置信传播和调查传播技术。

Dec, 2006

研究了在 $k$-SAT 问题中寻找满足分配的算法任务，证明了低次数多项式算法类无法在特定子密度下解决该问题，这是关于任何算法类在与 Fix 相等水平难度下的首个困难结果。

Jun, 2021

研究在随机图 G (n,p) 上的独立数和色数及其相应的松弛值，提出了一种改进的算法来近似计算独立数，同时对于判断 G (n,p) 是否可着色的算法提出了改进方法，并计算了边概率 p 范围内松弛值的渐近值。

Jun, 2003

提出了一种确定性算法，用于大致计算图的列表着色数量及离散马尔可夫随机场模型的分区函数，该算法基于统计物理学中的相关性衰减现象，并且不需要最强的计数技术。

Jun, 2006

本文探讨了 RQAOA 算法在 MAX-k-CUT 问题上的应用，进行了经典算法和量子经典混合算法的比较，并发现 level-1 的 RQAOA 算法可以优于现有 SDP 基础的经典算法，该算法可能是 NISQ 设备的有用算法。

Nov, 2020

使用单个样本估计具有硬约束的马尔可夫随机场的参数，算法基于伪似然估计器，对于 $k$-SAT 和 proper coloring 模型以及一般的 $H$-coloring 模型，不仅获得了正面结果，还获得了负面结果。

Nov, 2023