Prepared under the advice of Rémi Monasson at the Laboratory of theoretical physics of the École Normale Supérieure (Paris, France)
Defended on September 26th, 2006.
Title: Application of statistical mechanics to three out-of-equilibrium problems: algorithms, epidemics, granular media
Keywords: statistical mechanics, non-equilibrium systems, combinatorial optimization, stochastic processes, granular media, integrable systems
Abstract:
In this Ph. D. thesis, we study three problems using tools from the statistical mechanics. We show the existence of the phenomenon of critical universality for the dynamical phase transition of some combinatorial search algorithms. We give the exact values of the critical exponents and an analytic formula for a scaling function. We develop a formalism which enables us to compute a systematic perturbative expansion, in high space dimensions, of the large deviations function of the metastable state of the contact process. It can be reused e.g. for other models from the biology of populations. We introduce two exactly solvable 2D models for the statics of granular media. They reproduce the jamming transition and allow to discuss the different length scales of these media and to prove the Edwards hypothesis wrong in a realistic case.
| Jean-Philippe Bouchaud | Examiner | Directeur de recherche | S.P.E.C., C.E.A., Saclay |
| David Dean | Referee | Full Professor | LPTT, Université Paul Sabatier (Toulouse) |
| Olivier Martin | Examiner | Full Professor | LPTMS, Université Paris-Sud (Orsay) |
| Rémi Monasson | Guest (PhD advisor) | Chargé de recherche | CNRS, LPTENS, Paris |
| Nicolas Sourlas | Advisor | Directeur de recherche | CNRS, LPTENS, Paris |
| Frédéric van Wijland | Referee | Associate professor | Laboratoire MSC, Université Denis Diderot — Paris 7 |
| Jean-Bernard Zuber | Head | Full Professor | LPTHE, Université Pierre et Marie Curie — Paris 6 |
| Report on the thesis by Pr. David DEAN: | PostScript | |
| Report on the thesis by Frédéric VAN WIJLAND: |
Report of the examining committee:
Mr. Christophe Deroulers has presented his work on the application
of statistical mechanics to problems that one may qualify as
``out of equilibrium'': algorithms and their phases transitions, epidemic
propagation, and granular media treated by exact methods.
In his written thesis as well as in his oral presentation, he
demonstrated his outstanding qualities: curiosity and independence in the
choice of handled topics, technical virtuosity in their resolution et
mastering of all handled topics, from algorithmics to numerical
simulations via integrable systems.
This also appeared in the answers to the questions of the committee
members, where Ch. Deroulers showed much maturity and authority.
This thesis is regarded by the committee as extremely impressive by its
diversity and opening many perspectives. The committee thus awards the
title of Doctor of the University Pierre et Marie Curie—Paris 6 to
Mr. Christophe Deroulers with the mention très
honorable.
Abstract of each of the three parts:
| 1. The universality class of unitary propagation | 2. The lifetime of the metastable state of the contact process | 3. Two exactly solved models for the statics of granular media |
After briefly presenting the field of the analysis of algorithms, to which the work of this first part may belong, we recall some known facts about phase transition in combinatorial analysis. Then we introduce the constrain satisfaction problems and combinatorial optimization problems as well as some algorithms one uses to solve them, where we finally show, in the special case of complete algorithms for solving the decision problem of random satisfiability with the so-called unitary propagation heuristics, that a critical universality class exists. We give the exact values of its critical exponents and, when it is possible, an analytical form of the scaling function. |
In this part, we describe a formalism to study stochastic processes defined only through kinetical rules and we apply it to the perturbative computation (in high space dimension) of the large deviation function of the metastable state of the contact process. Chapter 7 gives examples of such processes and introduces the contact process. Chapter 8 gives the motivation and describes the formalism that we have introduced; it is similar to the dynamical mean-field theory (DMFT) used in the physics of strongly correlated electrons in solids. Finally, chapter 9 gives applications of this formalism, mainly to the contact process. |
This part studies in which respect the statics of granular media may be modelled, in a thermodynamic approach like the one of Edwards, by exactly solved models on 2D lattices. We first explain some elements of the physics of dry granular media and especially of their statics (chapter 11). A relatively extended introduction to exactly solved (or integrable) models on 2D lattices follows (chapter 12), then the building of two new exactly solved models and the discussion of their properties to which we have analytical access (chapter 13), the explanation and the discussion of the principle of the Monte Carlo simulations that were used to study other properties of these models (chapter 14), and a discussion of the features of the statics of granular media that these models reproduce (chapter 15). |