Forum de Physique Statistique à l'École Normale Supérieure

Next seminar

17 December,  Zohar Nussinov

Can we solve some hard problems locally? Possible relations between solvability and critical behaviors

Limited resources may motivate breaking large-scale problems into small ``local'' pieces and then stitching the so-found solutions. We explore the physics underlying this approach and ``local hardness" (complexity from the local solver perspective) in determining both NP and P-hard spin glass and other system ground states. Errors result from critical instabilities with gapless avalanche-like excitations having fractal boundaries. Within numerical accuracy, the geometrical size of these avalanches appears to conform to universal power-law distributions. Away from criticality, the local solvers rapidly become accurate. We further investigate more broadly the effects of varying only a single link on the ground states and the relation between complexity, critical behaviors, and mechanical chaos in clustering (community detection) problems and their continuum duals. Lastly, we will study the number of ground states of spin glass systems with continuous Gaussian couplings and prove that the latter degeneracy is not unique and depends subtlety on the order in which (i) the thermodynamic limit and (ii) the continuous real number limit of the coupling constants are taken.

Upcoming seminars

8 Janurary, Francesca Mignacco (special talk, Thursday 16h)

14 January, Friedrich Huebner

28 Janurary, Mikhail Feigelman 

4 February, Bastien Lapierre

18 February, Max McGinley 

25 March, Laura Foini

1 April, Clément Hongler

8 April, Jean-Noël Fuchs

15 April, Sarah Loos