Version française

PhD thesis of Christophe Deroulers

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, keywords, abstract

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


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.

Examining committee members

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

Reports of the referees and of the examining committee

Report on the thesis by Pr. David DEAN: PDF 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.

PhD thesis Manuscript

PDF document, 354 pages, 5.3 MB, A4 paper size, in French

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).

Back to the main page

Version française

Valid HTML 4.0!