Algorithms and Dynamics under Phase Transition Phenomena

该建议的目的是在一个基本的优化问题上取得进展：随机约束满足问题(RCSP)。来自统计物理的一些巧妙的但在数学上不严格的理论为rCSP的研究提供了一个新的视角；所谓的腔方法对rCSP的最基本性质做出了一些非常令人印象深刻的预测。我们的目的是研究腔方法关于各种rCSP模型上吉布斯分布结构的一些最基本预测的合理性。此外，我们打算研究rCSP的一些最重要的局部算法，如消息传递算法、Glauber Dynamic、Metropolis Process以及本项目的Prime Investigator最近提出的一个新算法。

The proposal aims at making advances in a fundamental optimisation problem: random Constraint Satisfaction Problems (rCSP). Some ingenious however mathematically non-rigorous theories from statistical physics have given the study of rCSP a new perspective; the so-called Cavity Method makes some very impressing predictions about the most fundamental properties of rCSP.Our aim is to investigate the soundness of some of the most basic predictions of the Cavity Method regarding the structure of the Gibbs distribution on various rCSP models. Further, we intend to study some of the most important local algorithms for rCSP like Message Passing Algorithms, Glauber Dynamics, Metropolis process, and a new algorithm suggested recently by the Prime Investigator of this project.