Computational Studies of Complex and Disordered Systems

University Of Massachusetts Amherst, Amherst MA

Investigators

Abstract

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.