Complex behavior for numerically simple problems
Alexander K. Hartmann (Institute for Physics, University of Oldenburg, Germany)
The description of complex system by the concept of Replica Symmetry Breaking (RSB) was shaped by Giorgio Parisi in the 1980s to solve the mean-field spin glass, as honored by the Nobel price in 2021. RSB has been used to analyze systems such as spin glasses, neural networks, optimization problems, or machine learning. Unfortunately, numerically these well known RSB-exhibiting problems are difficult since only exponential-time exact algorithm are available.
Here two models are considered, directed polymers in random media and increasing subsequences, called Ulam’s problem for the ground states. These models are interesting in many ways. For example, the distributions of free energies or sequence lengths, respectively, exhibit complex large-deviation behavior, which can be numerically addressed by rare-event sampling algorithms.
For both models it is possible to sample exactly in perfect thermal equilibrium with polynomial-time algorithms. This means, large
system sizes are accessible, in contrast to, e.g., the case of spin glasses. The results from perfect sampling of some problem disorder ensembles indicate the presence of RSB with complex structured landscapes. Thus, the study of complex RSB behavior is accessible numerically for some models.