Algorithms and Dynamics under Phase Transition Phenomena

该提案旨在推进一个基本的优化问题：随机约束满足问题（rCSP）。一些巧妙的，但数学上不严格的理论，从统计物理给研究的rCSP一个新的视角，所谓的腔方法作出了一些非常令人印象深刻的预测的最基本的性质rCSP。我们的目的是调查的合理性的一些最基本的预测的腔方法关于吉布斯分布的结构在各种rCSP模型。此外，我们打算研究一些最重要的本地算法的rCSP像消息传递算法，Glauber动力学，大都会过程，和一个新的算法最近建议的主要研究者这个项目。

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.