### Next seminar : Séminaire du LPTMS : Guilhem Semerjian (LPENS)

##### Tuesday, February 01 2022 at 11:00:00

## The planted matching problem

### Guilhem Semerjian (**Laboratoire de Physique** de l'Ecole Normale Supérieure)

ZOOM seminar.
Link: https://cnrs.zoom.us/j/95169859401?pwd=RUk5UVU4c05aVHRJcko4NnFWVVVldz09
Meeting ID: 951 6985 9401
Passcode: AsC43q
This talk will present some results, obtained with statistical mechanics techniques, on the planted matching problem. The latter is an inference problem, where the goal is to recover a perfect matching hidden (planted) in a weighted graph, the weights on the planted and non-planted edges being drawn with two different distributions.
Joint work with Gabriele Sicuro and Lenka Zdeborova.### Last Highlight : A short perspective on Giorgio Parisi’s achievements

Giorgio Parisi belongs to a rare class of universal scientists. His large breadth of interests and creative intuition has led to a wealth of ideas in remote areas of Science. Over more than 50 years, he made seminal contributions to Quantum Field Theory, Fluid Dynamics, the construction of Supercomputers, Numerical Simulations, Theoretical Biology, Collective Animal Motion and more. The Altarelli-Parisi equations in QCD, the Kardar-Parisi-Zhang interface growth equations, the Multifractal nature of Turbulence, the mechanism of Stochastic Resonance, the pioneering study of the dynamics of Starling Flocks are just but a few of his fundamental contributions to science. It is however in the field of Statistical Physics and Complex and Disordered Systems that he obtained his most original results, contributing to considerably widen the scope of the discipline. Parisi's journey in the physics of disordered systems began towards the end of the theoretical physics golden decade of the 1970’s, on his way back to Rome, after two prolific years in France as a visiting scientist at IHES and Ens in Paris. At that time, condensed matter theoreticians like Phil Anderson, Sam Edwards, David Thouless, to cite a few, were interested in the properties of strange disordered magnets called ‘Spin Glasses’. These are systems of magnetic moments (or spins) in interactions where the strength, as well as the sign of couplings between them, are effectively random. The system is said to be `frustrated’: it is impossible to find a configuration of the spins minimizing all the terms of the energy at the same time. Theoretically, Edwards and Anderson had proposed the ‘replica trick’, where the disordered interactions could be traded in favor of perfectly ferromagnetic interactions between n replicas of the original system, with the caveat that a strange limit of the number n tending to zero had to be taken at the end of the computation. Early attempts by David Sharrington and Scott Kirkpatrick to use replicas on a solvable model of a Spin Glass led to inconsistencies. Parisi found the exact solution of the Sherrington-Kirkpatrick spin glass in 1979, proposing an astonishing symmetry breaking pattern of the permutation group of n elements in the limit n → 0. The use of a daringly unconventional mathematical formalism together with difficulties of interpretations of the Parisi Replica Symmetry Breaking, later called RSB by the practitioners, generated a lot of enthusiasm, but also some skepticism in the community. After a few years, in the first half of the 1980s, the meaning of RSB was clarified, mainly by Parisi and his collaborators (Marc Mézard, Gérard Toulouse, Nicolas Sourlas, Miguel Virasoro), and independently by Bernard Derrida. Replica Symmetry Breaking was encoding for a glassy phase, with many possible equilibria organized in a hierarchical tree of states. Moreover, Mézard Parisi and Virasoro were able to recover the replica results by a more conventional physical ansatz called Cavity Method. In trying to explain the freezing properties of disordered magnets, a new deep organization of matter emerged. Paraphrasing N. Sourlas, Parisi’s RSB became the third known pattern of phase transition after Landau-Wilson symmetry breaking and Berezinskii-Kosterlitz-Thouless topological transitions. The mathematization of these results has required more than 25 years, culminating in the work of Francesco Guerra and Michel Talagrand in the years 2000.

But this is just the beginning of a long story that is lasting till today. The high interdisciplinary potential of the theoretical methods invented by Parisi in the new field of Complex Systems soon became evident: Statistical Physics was enlarging its scope beyond the premises of Condensed Matter Physics, to study Collective Phenomena in Biology, Neurosciences, Computer Science, Sociology, Economics Mathematics and more. In this change of perspective, the results of Spin Glass theory remain as one, perhaps the, most profound methodological tool. Strong and lasting ties ensued between Rome and Paris, that led the foundation of a school which has a deep influence in the landscape of the research in statistical physics in the Paris area. The LPTMS is proud to be part of these developments, and congratulates Giorgio Parisi for his beautiful prize.

Silvio Franz et Christophe Texier pour le graphisme, Oct 5 2021