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.
The main outcomes of the award were to advance the state-of-the-art in computer simulations of complex systems, help resolve long-standing fundamental questions in the behavior of a class of complex systems known as spin glasses, and to advance our knowledge of how parallel computing may help to understand and predict complex systems. A spin glass is a type of disordered magnetic material. Theoretical models of spin glasses are closely related to a broad class of computer science problems called combinatorial optimization problems. Our large-scale computational study of spin glasses thus advances knowledge in materials science and sheds light on the nature of an important class of computational problems that occur across the sciences and in industry. In addition to pushing forward the frontiers of simulations of spin glasses by going to larger systems at low temperature, we also introduced a new statistic that clearly distinguishes between two competing theories of the low temperature behavior of the material. Our results point toward one of these theories, known as the "droplet model." Our results help resolve a controversy in the statistical physics of disordered systems that has existed for more than 25 years. The algorithm used in the spin glass study is called "parallel tempering." Parallel tempering is widely used in physics, chemistry and computational biology to simulate complex thermodynamic systems with large free energy barriers. We advanced the understanding of this algorithm by analyzing its behavior in the setting of a well-defined model thermodynamic system with a large free energy barrier. We quantified how parallel tempering overcomes the problem of large free energy barriers and also demonstrated how it fails to overcome more subtle computational difficulties present in spin glass modeling and other combinatorial optimization problems. This work paves the way for improving parallel tempering and designing alternative, even more efficient, algorithmic methods for complex thermodynamic systems. We also explored a relatively unknown alternative to parallel tempering known as "population annealing" and showed that it has considerable promise. We carried out work that connects physics and theoretical computer science analyzing the computational complexity of predicting the behavior of Boolean logic circuits. This works shows, for the first time, the existence of phase transitions in the difficulty of solving problems in parallel. It also sheds light on how concepts from the theory of computational complexity may be applied to quantify the complexity of natural systems. In addition to these major results, we also carried out computational studies of several other systems of interest in statistical physics. The award also trained three Ph.D. students, one M.Sc. student and four undergraduate students in statistical physics and computational methods.
