[Séminaire Exceptionnel] Alexander Hartmann (Oldenburg)

Replica Symmetry breaking for Ulam's problem

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. Unfortunaley, numerically these well know RSB-exhibiting problems are difficult since only exponential-time exact algorithms are available.

Here two models are considered, directed polymers in random media and increasing subsequences, called Ulam's problem for the ground states, i.e. longest subsequences. The distributions of free energies or sequence lengths, respectively, exhibit complex large-deviation behavior, which can be numerically addressed by rare-event sampling algorithms.

Furthermore, 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 conveniently accessible numerically for some models.

Finally, for partially presorting random sequences, obe obtains a transition similar to a ferromagnet-spin glass transition.