Computational Studies of Complex and Disordered Systems

该奖项支持建立在统计物理学和计算复杂性理论之间协同作用的理论研究和教育。学生将参与跨学科研究并获得对材料模拟、蛋白质折叠和组合优化有价值的技能。建议的研究分为三个主要部分。第一个项目解决了如何从简单的规则和随机性中自发地产生物理复杂性，第二个项目专注于受挫系统的图形表示，第三个项目涉及开发蒙特卡罗算法来处理受挫系统。计算复杂性理论寻求确定解决问题所需的计算资源。相变发生在解决计算问题的复杂性中，统计物理方法非常适合于理解导致这种相变的机制。该方法将应用于电路数值问题和达尔文进化论。具有竞争相互作用和受挫的无序自旋系统将使用图形表示和相关的高效集群算法来研究什么决定了选择哪个阶段：初始条件还是演化过程中的选择。诸如复制交换、蒙特卡罗和进化退火法等计算算法将被优化。非技术总结该奖项支持在统计物理和计算复杂性理论之间前沿的理论研究和教育。计算复杂性理论试图确定解决达尔文进化论等问题所需的计算资源。解决问题的复杂性发生了戏剧性的变化，统计物理的方法非常适合于理解导致复杂性变化的机制。学生将从事跨学科研究，并获得对材料模拟、蛋白质折叠和组合优化有价值的技能。

TECHNICAL SUMMARY This award supports theoretical research and education that is built on the synergy between statistical physics and computational complexity theory. Students will participate in interdisciplinary research and gain skills valuable for materials simulation, protein folding, and combinatorial optimization.The proposed research is organized into three main parts. The first project addresses how physical complexity can emerge spontaneously from simple rules and randomness, the second project focuses on graphical representation for frustrated systems, and the third involves the development of Monte Carlo algorithms to deal with frustrated systems. Computational complexity theory seeks to determine the computational resources required to solve problems. Phase transitions occur in the complexity of solving computational problems and the methods of statistical physics are well suited to understand the mechanisms leading to such phase transitions. The approach will be applied to circuit value problems and Darwinian evolution. Disordered spin systems with competing interaction and frustration will be investigated using graphical representations and associated efficient cluster algorithms to investigate what determines which phase is selected: the initial conditions or the choices during evolution. Computational algorithms such as replica exchange Monte Carlo and evolutionary annealing will be optimized.NONTECHNICAL SUMMARY This award supports theoretical research and education at the frontier between statistical physics and computational complexity theory. Computational complexity theory seeks to determine the computational resources required to solve problems such as Darwinian evolution. Dramatic changes occur in the complexity of solving problems and the methods of statistical physics are well suited to understand the mechanisms leading to such variations in the complexity.Students will be engaged in interdisciplinary research and gain skills valuable for materials simulation, protein folding, and combinatorial optimization.