Speaker
Description
In large random systems, certain behaviors are reliably predicted, like the energy density of the ground state. The long-time behavior of many physical and algorithmic dynamics is likewise predictable, through DMFT and related approaches. But can these behaviors be connected to static structures of the problem at hand, like its energy landscape? Recently, development of the Overlap Gap Property, which depends on the existence of a system-spanning component of the energy level set, suggests that static topological properties can predict the performance of the best algorithms. Here, I will describe progress towards predicting the performance of the mediocre but simple algorithms we usually use. We use the ergodicity of a random walker to probe whether typical configurations belong to a system-spanning component of the energy level set. Passive random walkers lose ergodicity at a depth associated with the glass transition, but active random walkers remain ergodic to greater depth. We argue that in the limit of infinite persistence time, the ergodicity-breaking transition coincides with the point at which system-spanning components become atypical, and discuss connections with gradient descent dynamics.
