Collaborative Research FRG: Phase Transitions in Stochastics Dynamics and Algorithms

几十年来，物理学家一直在研究自旋系统的Dembo随机动力学，以此作为模拟Gibbs测量的一种手段。在过去的十年里，计算机科学家和概率学家为这项研究带来了新的视角和方法，并展示了它对组合结构的近似均匀抽样和近似计数的适用性。控制这种采样方案运行时间的关键因素是动力学的混合时间，当潜在的静态测量经历相变时，动力学的混合时间可以发生巨大的变化。这个FRG项目的一个中心目标是系统地探索信息理论、大偏差和马尔可夫链混合时间之间的联系。某些基本的优化和搜索问题(例如，具有随机子句的k-可满足性)随着输入大小和未知参数的数量之间的比率被调整而表现出根本的变化。定量地了解这些门槛是该项目的另一个重点。当输入的微小变化对系统的行为产生深刻的、定性的影响时，系统就经历了“相变”。相变的例子在物理学中已经研究了几十年；最近，这个概念在其他领域变得重要起来，特别是在搜索和优化技术的性能方面。在这个课题的难题上取得进一步进展需要概率和算法方面的研究人员的长期合作，以及与组合数学和统计物理相关领域的专家的咨询。该项目预计将对随机化算法的设计和分析产生影响，并对关键的调度和优化问题提供见解。随着学生学习不同学科的语言和工具，离散概率和计算机科学的研究生培训预计将产生重大影响。

0244323Dembo Stochastic dynamics for spin systems have been investigated for decades by physicists as a means for simulating Gibbs measures. In the last decade, computer scientists and probabilists have brought new perspectives and methods to this study and showed its applicability to approximately uniform sampling, and approximate counting of combinatorial structures. The key factor controlling the running time of such sampling schemes is the mixing time of the dynamics, which can change dramatically when the underlying stationary measure undergoes a phase transition. A central aim of this FRG project is to explore systematically the connections between information theory, large deviations, and mixing times for Markov chains. Certain fundamental optimization and search problems (e.g., k-satisfiability with random clauses) exhibit a radical change as the ratio between the input size and the number of unknown parameters is tuned. Understanding these thresholds quantitatively is another focus of the project. A system undergoes a "phase transition" when a small change in its input has a profound, qualitative effect on its behavior. Examples of phase transitions have been studied for decades in physics; more recently, this notion has become important in other areas, notably in connection with the performance of search and optimization techniques. Further progress on the hard problems of the subject requires long-term cooperation of researchers in probability and algorithms, as well as consultation with experts in the adjoining areas of combinatorics and statistical physics. The project is expected to have an impact on the design and analysis of randomized algorithms and provide insight on key scheduling and optimization problems. Significant effects on graduate training of students in discrete probability and computer science are expected, as they learn the language and tools of the different disciplines involved.