标题： 关于随机$k$-SAT Gibbs 唯一性阈值的再探讨 显示英文标题

标题： The random $k$-SAT Gibbs uniqueness threshold revisited

摘要： 我们证明，对于任意的 $k\geq3$，当子句/变量比值不超过相应Galton-Watson树的Gibbs唯一性阈值时，随机 $k$-SAT公式满足赋值的数量由物理学方法[Monasson, Zecchina: Phys. Rev. Lett. (1996)]预测的“ Replica 对称解”给出。此外，虽然对于任意的 $k\geq3$，Gibbs唯一性阈值仍未被精确确定，但我们得出了该阈值的新下界，改进了先前的工作[Montanari 和 Shah: SODA (2007)]。尤其对于较小的 $k$，这种改进意义重大。 显示英文摘要

摘要： We prove that for any $k\geq3$ for clause/variable ratios up to the Gibbs uniqueness threshold of the corresponding Galton-Watson tree, the number of satisfying assignments of random $k$-SAT formulas is given by the `replica symmetric solution' predicted by physics methods [Monasson, Zecchina: Phys. Rev. Lett. (1996)]. Furthermore, while the Gibbs uniqueness threshold is still not known precisely for any $k\geq3$, we derive new lower bounds on this threshold that improve over prior work [Montanari and Shah: SODA (2007)].The improvement is significant particularly for small $k$.