Dynamical regimes of diffusion models.

We study generative diffusion models in the regime where both the data dimension and the sample size are large, and the score function is trained optimally. Using statistical physics methods, we identify three distinct dynamical regimes during the generative diffusion process. The generative dynamics, starting from pure noise, first encounters a speciation transition, where the broad structure of the data emerges, akin to symmetry breaking in phase transitions.

Exponential Capacity of Dense Associative Memories.

Recent generalizations of the Hopfield model of associative memories are able to store a number P of random patterns that grows exponentially with the number N of neurons, P=exp(αN). Besides the huge storage capacity, another interesting feature of these networks is their connection to the attention mechanism which is part of the Transformer architecture widely applied in deep learning. In this work, we study a generic family of pattern ensembles using a statistical mechanics analysis which gives exact asymptotic thresholds for the retrieval of a typical pattern, α_{1}, and lower bounds for the maximum of the load α for which all patterns can be retrieved, α_{c}, as well as sizes of attraction basins.

Matrix factorization with neural networks.

Matrix factorization is an important mathematical problem encountered in the context of dictionary learning, recommendation systems, and machine learning. We introduce a decimation scheme that maps it to neural network models of associative memory and provide a detailed theoretical analysis of its performance, showing that decimation is able to factorize extensive-rank matrices and to denoise them efficiently. In the case of binary prior on the signal components, we introduce a decimation algorithm based on a ground-state search of the neural network, which shows performances that match the theoretical prediction.

Epidemic mitigation by statistical inference from contact tracing data.

Contact tracing is an essential tool to mitigate the impact of a pandemic, such as the COVID-19 pandemic. In order to achieve efficient and scalable contact tracing in real time, digital devices can play an important role. While a lot of attention has been paid to analyzing the privacy and ethical risks of the associated mobile applications, so far much less research has been devoted to optimizing their performance and assessing their impact on the mitigation of the epidemic.

Mean-field message-passing equations in the Hopfield model and its generalizations.

Motivated by recent progress in using restricted Boltzmann machines as preprocessing algorithms for deep neural network, we revisit the mean-field equations [belief-propagation and Thouless-Anderson Palmer (TAP) equations] in the best understood of such machines, namely the Hopfield model of neural networks, and we explicit how they can be used as iterative message-passing algorithms, providing a fast method to compute the local polarizations of neurons. In the "retrieval phase", where neurons polarize in the direction of one memorized pattern, we point out a major difference between the belief propagation and TAP equations: The set of belief propagation equations depends on the pattern which is retrieved, while one can use a unique set of TAP equations. This makes the latter method much better suited for applications in the learning process of restricted Boltzmann machines.

Dynamic message-passing equations for models with unidirectional dynamics.

Understanding and quantifying the dynamics of disordered out-of-equilibrium models is an important problem in many branches of science. Using the dynamic cavity method on time trajectories, we construct a general procedure for deriving the dynamic message-passing equations for a large class of models with unidirectional dynamics, which includes the zero-temperature random-field Ising model, the susceptible-infected-recovered model, and rumor spreading models. We show that unidirectionality of the dynamics is the key ingredient that makes the problem solvable.

Inferring the origin of an epidemic with a dynamic message-passing algorithm.

We study the problem of estimating the origin of an epidemic outbreak: given a contact network and a snapshot of epidemic spread at a certain time, determine the infection source. This problem is important in different contexts of computer or social networks. Assuming that the epidemic spread follows the usual susceptible-infected-recovered model, we introduce an inference algorithm based on dynamic message-passing equations and we show that it leads to significant improvement of performance compared to existing approaches.

Level statistics of disordered spin-1/2 systems and materials with localized Cooper pairs.

The origin of continuous energy spectra in large disordered interacting quantum systems is one of the key unsolved problems in quantum physics. Although small quantum systems with discrete energy levels are noiseless and stay coherent forever in the absence of any coupling to external world, most large-scale quantum systems are able to produce a thermal bath and excitation decay. This intrinsic decoherence is manifested by a broadening of energy levels, which aquire a finite width.

Mean-field behavior of the negative-weight percolation model on random regular graphs.

We investigate both analytically and numerically the ensemble of minimum-weight loops in the negative-weight percolation model on random graphs with fixed connectivity and bimodal weight distribution. This allows us to study the mean-field behavior of this model. The analytical study is based on a conjectured equivalence with the problem of self-avoiding walks in a random medium.

Disorder-driven quantum phase transitions in superconductors and magnets.

We develop an analytical theory, based on the quantum cavity method, describing the quantum phase transitions in low-temperature, strongly disordered ferromagnets and superconductors. At variance with the usual quantum critical points, we find a phase diagram with two critical points separating three phases. When the disorder increases, the systems goes from the ordered phase to an intermediate disordered phase characterized by activated transport and then to a second disordered phase where no transport is possible.

Emergence of rigidity at the structural glass transition: a first-principles computation.

We compute the shear modulus of structural glasses from a first-principles approach based on the cloned liquid theory. We find that the intrastate shear modulus, which corresponds to the plateau modulus measured in linear viscoelastic measurements, strongly depends on temperature and vanishes continuously when the temperature is increased beyond the glass temperature.

Hierarchical random energy model of a spin glass.

We introduce a random energy model on a hierarchical lattice where the interaction strength between variables is a decreasing function of their mutual hierarchical distance, making it a non-mean-field model. Through small coupling series expansion and a direct numerical solution of the model, we provide evidence for a spin-glass condensation transition similar to the one occurring in the usual mean-field random energy model. At variance with the mean field, the high temperature branch of the free-energy is nonanalytic at the transition point.

Constraint satisfaction problems and neural networks: A statistical physics perspective.

A new field of research is rapidly expanding at the crossroad between statistical physics, information theory and combinatorial optimization. In particular, the use of cutting edge statistical physics concepts and methods allow one to solve very large constraint satisfaction problems like random satisfiability, coloring, or error correction. Several aspects of these developments should be relevant for the understanding of functional complexity in neural networks.

Locked constraint satisfaction problems.

We introduce and study the random "locked" constraint satisfaction problems. When increasing the density of constraints, they display a broad "clustered" phase in which the space of solutions is divided into many isolated points. While the phase diagram can be found easily, these problems, in their clustered phase, are extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions.

Statistical mechanics of the hitting set problem.

In this paper we present a detailed study of the hitting set (HS) problem. This problem is a generalization of the standard vertex cover to hypergraphs: one seeks a configuration of particles with minimal density such that every hyperedge of the hypergraph contains at least one particle. It can also be used in important practical tasks, such as the group testing procedures where one wants to detect defective items in a large group by pool testing.

Landscape of solutions in constraint satisfaction problems.

We present a theoretical framework for characterizing the geometrical properties of the space of solutions in constraint satisfaction problems, together with practical algorithms for studying this structure on particular instances. We apply our method to the coloring problem, for which we obtain the total number of solutions and analyze in detail the distribution of distances between solutions.

Cavity approach to the random solid state.

The cavity approach is used to address the physical properties of random solids in equilibrium. Particular attention is paid to the fraction of localized particles and the distribution of localization lengths characterizing their thermal motion. This approach is of relevance to a wide class of random solids, including rubbery media (formed via the vulcanization of polymer fluids) and chemical gels (formed by the random covalent bonding of fluids of atoms or small molecules).

Lossy data compression with random gates.

We introduce a new protocol for a lossy data compression algorithm which is based on constraint satisfaction gates. We show that the theoretical capacity of algorithms built from standard parity-check gates converges exponentially fast to the Shannon's bound when the number of variables seen by each gate increases. We then generalize this approach by introducing random gates.

Toward a theory of marker-assisted gene pyramiding.

We investigate the best way to combine into a single genotype a series of target genes identified in different parents (gene pyramiding). Assuming that individuals can be selected and mated according to their genotype, the best method corresponds to an optimal succession of crosses over several generations (pedigree). For each pedigree, we compute the probability of success from the known recombination fractions between the target loci, as well as the number of individuals (population sizes) that should be genotyped over successive generations until the desired genotype is obtained.

Physics/computer science. Passing messages between disciplines.

Problems in computer science, such as error correction in information transfer and "satisfiability" in optimization, show phase transitions familiar from solid-state physics. In his Perspective, Mézard explains how recent advances in these three fields originate in similar "message passing" procedures. The exchange of elaborate messages between different variables and constraints, used in the study of phase transitions in physical systems, helps to make error correction and satisfiability codes more efficient.

Random K-satisfiability problem: from an analytic solution to an efficient algorithm.

We study the problem of satisfiability of randomly chosen clauses, each with K Boolean variables. Using the cavity method at zero temperature, we find the phase diagram for the K=3 case. We show the existence of an intermediate phase in the satisfiable region, where the proliferation of metastable states is at the origin of the slowdown of search algorithms.

Lattice glass models.

Motivated by the concept of geometrical frustration, we introduce a class of statistical mechanics lattice models for the glass transition. Monte Carlo simulations in three dimensions show that they display a dynamical glass transition which is very similar to that observed in other off-lattice systems and which does not depend on a specific dynamical rule. A mean-field study shows the existence of a discontinuous glass transition, in agreement with the numerical observations.