Collaborative Research FRG: Phase Transitions in Stochastics Dynamics and Algorithms

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

0244479Peres 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.