Main Page

From Werner KRAUTH

(Difference between revisions)
Jump to: navigation, search
Revision as of 23:58, 22 January 2025
Werner (Talk | contribs)
(→Research over the ages)
← Previous diff		 Current revision
Werner (Talk | contribs)
(→Velocity Trapping in the Lifted TASEP and the True Self-Avoiding Random Walk)
Line 26: Line 26:
Here is hidden text Here is hidden text
--> -->
-=Oxford Lectures 2025=+=Oxford Lectures 2026=
-Since 2023, I have enjoyed myself tremendously as Visiting Professor in Physics at the University of Oxford where, again this year, I spend several months, heavily engaged in research within an incredibly active and collaborative environment. I also teach a set of public lectures on [https://www.physics.ox.ac.uk/events/algorithms-and-computations-theoretical-physics-set-lectures Algorithms and Computations in theoretical physics] (see the announcement for a syllabus). Lecture notes will be made available [[Oxford_Lectures_2025|here]], as we go. +
-I am very grateful to the Department and the University to have arranged for me to lecture on one of my favorite subjects, and also to have made these lectures "public". Anyone can attend: Students at the Oxford Physics department (or not), postdocs (or not), even the general public. This year's lecture series started on 21 January 2025.+Since 2023, I have enjoyed myself tremendously as Visiting Professor in Physics at the University of Oxford where, again this year, I spend several months. I'm heavily engaged in research within an incredibly active and collaborative environment. I also give a set of public lectures on [https://www.physics.ox.ac.uk/events/algorithms-and-computations-theoretical-physics-set-lectures-2026 Algorithms and Computations in theoretical physics] (see the announcement for a syllabus). [[Oxford_Lectures_2025|Lecture notes are available]], and will be updated [https://www.collinsdictionary.com/dictionary/french-english/au-fil-de-l-eau "with the flow of the water"], as we say in French.
-[[Image:OxfordLectures2025.png|100px|right|frame|Public Lectures at University of Oxford, Tuesdays 2-4pm, 21 January through 11 March 2025 ]]+ 
 +I am very grateful to the Department and the University to have arranged for me to lecture on one of my favorite subjects, and also to have made these lectures "public". Anyone can attend: Students at the Oxford Physics department (or not), postdocs (or not), young and old, from all walks of life. This year's lectures start on 20 January 2026, and they take place every Tuesday afternoon at 2pm until 10 March 2026.
 +[[Image:OxfordLectures2025.png|100px|right|frame|Public Lectures at University of Oxford, Tuesdays 2-4pm, 20 January through 10 March 2026 ]]
<br clear="all" /> <br clear="all" />
 +
=Research over the ages= =Research over the ages=
A (big) number of months ago, in 1988-89 (sic!), we were fascinated by a certain problem in the then new field of neural-networks research, namely the binary perceptron. The question was about the storage capacity of the now famous Hopfield model that, in a certain continuous case, had long been proven to be 2N, a result due to Thomas M. A (big) number of months ago, in 1988-89 (sic!), we were fascinated by a certain problem in the then new field of neural-networks research, namely the binary perceptron. The question was about the storage capacity of the now famous Hopfield model that, in a certain continuous case, had long been proven to be 2N, a result due to Thomas M.
-Cover (1965) and reinterpreted by E. Gardner (1987). We found this result depressing, as it stated that you needed (with, here on the website, a few shortcuts) N real number in order to store 2N single bits 0 and 1. This is like paying N gold coins (floats) to buy 2N dimes (single bits), clearly a bad deal. So we were very interested in finding out what would happen in the '''binary''' perceptron where, instead of N real numbers (the weights of one row of the Hopfield net) you had N bits (the weights of the binary Hopfield net). Together with Manfred Opper, who then visited ENS (where I did my thesis), we wrote a computational paper, which quite clearly showed that the capacity was reduced from 2 (Cover's result) to a strange number very close to 0.82. At the time, we were quite proud of the two tricks which made our approach work namely, on the one hand, that we approximated the binary patterns with Gaussians patterns (which greatly improved the finite-size scaling), and that we used the Gray code for a certain enumeration job. A few months later, again in 1989, with Marc Mézard, I wrote another paper, where we conjectured, based on a one-step replica-symmetry-breaking calculation, that the critical capacity had to be equal to 0.833, a known function. In the conclusion of our 1989 paper, we speculated that our solution might well be exact+Cover (1965) and reinterpreted by E. Gardner (1987). We found this result depressing, as it stated that you needed (with, here on the website, a few shortcuts) N real numbers in order to store 2N single bits 0 and 1. This is like paying N gold coins (floats) to buy 2N copper dimes (single bits), clearly a bad deal. So we were very interested in finding out what would happen in the '''binary''' perceptron where, instead of N real numbers (the weights of one row of the Hopfield net) you had N bits (the weights of the binary Hopfield net). Together with Manfred Opper, who then visited ENS (where I did my thesis) from the University of Giessen in Germany, [https://iopscience.iop.org/article/10.1088/0305-4470/22/11/012 we wrote a computational paper], which quite clearly showed that the capacity was reduced from 2 (Cover's result) to a strange number very close to 0.82. At the time, we were quite proud of the two tricks which made our approach work namely, on the one hand, that we approximated the binary patterns with Gaussians patterns (which greatly improved the finite-size scaling) and, on the other hand, that we used [https://en.wikipedia.org/wiki/Gray_code the Gray code] for a certain enumeration job. A few months later, again in 1989, with Marc Mézard, [https://doi.org/10.1051/jphys:0198900500200305700 we conjectured], based on a one-step replica-symmetry-breaking calculation, that the critical capacity had to be equal to 0.833, a known function. In the conclusion of our 1989 paper, we speculated that our solution might well be exact
[[Image:KrauthMezard1989RED.png|100px|right|frame|... conclusions of a 1989 paper...]] [[Image:KrauthMezard1989RED.png|100px|right|frame|... conclusions of a 1989 paper...]]
<br clear="all" /> <br clear="all" />
-As I mentioned above, this was in 1989, before the bicentennial celebration of the French Revolution and many other events. For a fair number of years (months, I should say), the question of the critical capacity of the binary perceptron fascinated physicists, mathematicians and computer scientists, as it had first fascinated us. Then, early in 2024, a keystone paper was written by Brice Huang, a MIT graduate student in Mathematics. He completed an enormous body of previous works and was awarded the very prestigious [https://lids.mit.edu/news-and-events/news/brice-huang-receives-machtey-award-best-student-paper-focs-2024 Machtey award for best student paper in 2024]. Bravo, congratulations, and celebrations, Brice --- the long wait was worth it and, indeed, "'''some''' more analytical work had been required..."!+As I mentioned above, this was in 1989, before the bicentennial celebration of the French Revolution and many other events. For a fair number of years (months, I should say), the question of the critical capacity of the binary perceptron fascinated physicists, mathematicians and computer scientists, as it had first fascinated us. But it always appeared that "some more work" was "needed". Then finally, early in 2024, [https://arxiv.org/abs/2404.18902 a keystone paper] was written by Brice Huang, a MIT graduate student in Mathematics. He completed an enormous body of previous works, actually showed that our 0.833 had been correct all along. Brice was awarded the very prestigious [https://lids.mit.edu/news-and-events/news/brice-huang-receives-machtey-award-best-student-paper-focs-2024 Machtey award for best student paper in 2024]. Bravo, congratulations, and celebrations, Brice --- the long wait was worth it and, indeed, "'''some''' more analytical work had been required..."!
=Milestone Research= =Milestone Research=
-A [[Engel_et_al_2013| paper]], on a '''first'''-order transition in '''two''' dimensions, by a collaboration on '''three''' continents (!) that I published a few years ago in Physical Review E together with M. Engel, J. A. Anderson, S. C. Glotzer, M. Isobe, and E. P. Bernard, was chosen as the [https://journals.aps.org/pre/collections/pre-25th milestone article for 2013] by the journal's editorial board. This 2013 paper confirmed [[Bernard Krauth 2011| research published in 2011, in Physical Review Letters]], with Etienne Bernard, on what really goes on in two-dimensional melting. See [[Main_Page#Hard-disk_equation_of_state:_First-order_liquid-hexatic_transition_in_two_dimensions_with_three_simulation_methods| here]] for the story of the paper.+ 
 +A [[Bernard Krauth Wilson 2009| 2009 paper]] introducing the event-chain Monte Carlo algorithm was the object of a [https://kimreview.org/commentaries/10-25950-a25ce9a6/ commentary], in 2026, by Prof E.A.J.F. Peters, from the Eindhoven University of Technology, The Netherlands. The statement of significance of the commentary starts with: ''"The seminal 2009 paper by Bernard, Krauth, and Wilson marked a paradigm shift in Monte Carlo sampling. By abandoning the restrictive condition of detailed balance in favor of the more fundamental principle of global balance..."''
 + 
 +A [[Engel_et_al_2013| 2013 paper]], on a '''first'''-order transition in '''two''' dimensions, by a collaboration on '''three''' continents (!) that I published a few years ago in Physical Review E together with M. Engel, J. A. Anderson, S. C. Glotzer, M. Isobe, and E. P. Bernard, was chosen as the [https://journals.aps.org/pre/collections/pre-25th milestone article for 2013] by the journal's editorial board. This 2013 paper confirmed [[Bernard Krauth 2011| research published in 2011, in Physical Review Letters]], with Etienne Bernard, on what really goes on in two-dimensional melting. See [[Main_Page#Hard-disk_equation_of_state:_First-order_liquid-hexatic_transition_in_two_dimensions_with_three_simulation_methods| here]] for the story of the paper.
=Video recordings of research talks= =Video recordings of research talks=
Line 52: Line 57:
I am deeply interested in statistical and condensed-matter physics, often in connection to computation and algorithms. I am deeply interested in statistical and condensed-matter physics, often in connection to computation and algorithms.
Current interests are in hard spheres, mainly the melting transition in two-dimensional disks and in two-dimensional melting, bosons (in collaboration with the experimental groups at ENS), and the theory of convergence and of coupling in Markov chains. Recent work in my research group has led to the redefinition of the dominant Markov-chain Monte Carlo paradigm, namely the Metropolis algorithm. This has already allowed us to propose powerful algorithms for particle systems, continuous spin models and long-range systems, and to obtain important physical results. Research on the ''beyond-Metropolis'' paradigm, together with applications in classical and quantum physics and its interfaces will likely be a focus of my research activity in the next few years. Current interests are in hard spheres, mainly the melting transition in two-dimensional disks and in two-dimensional melting, bosons (in collaboration with the experimental groups at ENS), and the theory of convergence and of coupling in Markov chains. Recent work in my research group has led to the redefinition of the dominant Markov-chain Monte Carlo paradigm, namely the Metropolis algorithm. This has already allowed us to propose powerful algorithms for particle systems, continuous spin models and long-range systems, and to obtain important physical results. Research on the ''beyond-Metropolis'' paradigm, together with applications in classical and quantum physics and its interfaces will likely be a focus of my research activity in the next few years.
 +
 +==Velocity Trapping in the Lifted TASEP and the True Self-Avoiding Random Walk==
 +In 2024/25, three of my mathematician friends, Brune Massoulié, Clément Erignoux, Cristina Toninelli, (from ENS Paris, from University Paris Dauphine, and from INRIA Lyon) and I attempted to understand the astonishingly fast convergence of non-reversible Markov chains, represented by the lifted TASEP, a system of N hard core particles on a one-dimensional lattice of L sites, a model that I discuss below in more detail. It was already clear from previous work that the lifted TASEP possessed a '''pointer''', whose velocity was zero at a certain parameter alpha = N/L, in other words, the overall density. The velocity was negative for smaller densities and larger for larger ones. The first key insight of our [[Massoulie et al 2025|paper]] that resulted from this work was that the pointer could not possibly know how many particles N there were exactly on a lattice of L (imagine L=100.000.000.000). This brought us to a discussion in terms of the ''local'' density. Whereever the local density was a bit larger than the average N/L, the pointer would move forward, and it would move backwards at slightly lower local density. There is thus an evident density-velocity correlation that is absent in usual statistical mechanics. After a few intense work sessions (online between New York or Oxford, Paris and Lyon, and then in person at the ENS Math department), we came up with the concept of "velocity trapping" which, correctly formulated and mathematically formalized, gave a manuscript which was accepted for publication in Physical Review Letters, in 2025, not very long after we had submitted it. The paper contains a second key insight, namely the connection of the non-reversible Markov chains and, in particular, the lifted TASEP, to the wide field of True Self-avoiding random walks. The story is fascinating and it follows seminal observations by my friend A. C. "Tony" Maggs (ESPCI Paris) but is a bit complicated to explain on this website. You're invited to take a look at the [[Massoulie et al 2025|original paper]].
==Fast, approximation-free molecular simulation of the SPC/Fw water model using non-reversible Markov chains== ==Fast, approximation-free molecular simulation of the SPC/Fw water model using non-reversible Markov chains==
Line 64: Line 72:
The third paradox is the bundling of O(N) independent decisions to interrupt the straight-line trajectory of the The third paradox is the bundling of O(N) independent decisions to interrupt the straight-line trajectory of the
piecewise-deterministic Markov process into an expression that can be evaluated in constant time. The paper is openly accessible, and even all the computer code has been rendered open-source. piecewise-deterministic Markov process into an expression that can be evaluated in constant time. The paper is openly accessible, and even all the computer code has been rendered open-source.
- 
-==Fast, approximation-free molecular simulation of the SPC/Fw water model using non-reversible Markov chains== 
==Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains== ==Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains==
-In recent years, my colleagues and I have worked on a multitude of computational algorithms which improve on the classical methods. Specifically, we have worked on Monte Carlo algorithms based on non-reversible Markov chains. Such algorithms have had successes in applications but are generally difficult to analyze, resulting in a scarcity of exact results. In a recent manuscript [[Essler_Krauth_2023|Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains]] with my colleague Fabian Essler (Oxford), we introduce the “lifted” TASEP (totally asymmetric simple exclusion process) as a paradigm for non-reversible Markov chains. Our model can be viewed as a second-generation lifting of the reversible Metropolis algorithm on a one-dimensional lattice and is exactly solvable by an unusual kind of coordinate Bethe ansatz. We establish the integrability of the model and present strong evidence that the lifting leads to relax- ation on shorter timescales than in the KPZ (Kardar–Parisi–Zhang) universality class.+In recent years, my colleagues and I have worked on a multitude of computational algorithms which improve on the classical methods. Specifically, we have worked on Monte Carlo algorithms based on non-reversible Markov chains. Such algorithms have had successes in applications but are generally difficult to analyze, resulting in a scarcity of exact results. In a recent manuscript [[Essler_Krauth_2023|Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains]], now [https://doi.org/10.1103/PhysRevX.14.041035 published in Physical Review X] with my colleague [https://www.physics.ox.ac.uk/our-people/essler Fabian Essler (Oxford)], we introduce the “lifted” TASEP (totally asymmetric simple exclusion process) as a paradigm for non-reversible Markov chains. Our model can be viewed as a second-generation lifting of the reversible Metropolis algorithm on a one-dimensional lattice and is exactly solvable by an unusual kind of coordinate Bethe ansatz. We establish the integrability of the model and present strong evidence that the lifting leads to relaxation on shorter timescales than in the KPZ (Kardar–Parisi–Zhang) universality class.
 + 
 +Here the "Popular Summary" that accompanied our paper:
 + 
 +Markov-chain Monte Carlo (MCMC) algorithms formulate the sampling problem for complex probability distributions as a simulation of fictitious physical systems in equilibrium, where all motion is diffusive and time reversible. But nonreversible algorithms can, in principle, sample distributions much more efficiently. In recent years, a class of “lifted” Markov chains has implemented this idea in practice, but the resulting algorithms are extremely difficult to analyze. In this work, we introduce an exactly solvable paradigm for nonreversible Markov chains.
 + 
 +Our paradigm, which we term the lifted totally asymmetric simple exclusion process (TASEP), describes a particular type of nonreversible dynamics for particles on a one-dimensional lattice. We show that this dynamics allows for polynomial speedups in particle number compared to the famous Metropolis MCMC algorithm. The lifted-TASEP dynamics is, in fact, faster than that of any other known class of models. To arrive at our conclusions, we combine exact methods from the theory of integrable models with extensive numerical simulations. In particular, we prove that the lifted TASEP is integrable and determine the scaling of its relaxation and mixing times with system size.
 + 
 +Our work opens the door to obtaining mathematically rigorous results for speedups of nonreversible MCMC algorithms, and more generally, of lifted Markov chains arising in interacting many-particle systems.
 + 
Line 76: Line 91:
=Upcoming events= =Upcoming events=
 +
 +* University of Oxford (UK), Research stay 15 January - 14 March 2025 (Visiting Professor at the Department of Physics), [https://www.physics.ox.ac.uk/events/algorithms-and-computations-theoretical-physics-set-lectures-2026 Public lectures]
 +* Dresden (Germany), [https://www.pks.mpg.de/ Max Planck Institute for the Physics of Complex Systems], [https://www.pks.mpg.de/odcd25 One Dimension, Countless Directions, International Focus Workshop] 20 - 21 November 2025
 +* University of Oxford (UK), Research stay 14 October - 07 December 2025 (Visiting Professor at the Department of Physics)
 +* Trieste (Italy), [https://www.ictp.it/ International Centre for Theoretical Physics], [https://indico.ictp.it/event/10860 School on Quantum Dynamics of Matter, Light and Information] 30 August - 5 September 2025 (Invited lecture series "The second Markov-chain revolution)
 +* Roscoff (France), CECAM workshop "[https://www.cecam.org/workshop-details/crystallization-and-self-assembly-from-soft-matter-to-pharmaceuticals-to-biomineralisation-1420 Crystallization and Self-Assembly: from Soft Matter to Pharmaceuticals to Biomineralisation]" 5 - 7 May 2025 (Invited talk: [https://www.lps.ens.fr/%7Ekrauth/images/0/03/Roscoff.pdf Markov-chain sampling for long-range systems without evaluating total energies / forces])
 +* University of Florence (Italy), [https://www.ggi.infn.it/ Galileo Galilei Institute for Theoretical Physics], Winter School [https://www.ggi.infn.it/showevent.pl?id=493 SFT 2025 Lectures on Statistical Field Theories] 10 - 14 February 2025 (Lecture course: The second Markov-chain revolution).
 +* University of Tokyo, Komaba (Japan) 9th Workshop on Physics between ENS and UTokyo, 11-12 December 2024 (Co-organizer, Talk: Hamiltonian MC vs. event-chain MC: Sampling strategies beyond the diffusive regime)
 +* University of Cambridge (UK), Isaac Newton Institute for Mathematical Sciences, Workshop: [https://www.newton.ac.uk/event/ssdw04/ Monte Carlo sampling: beyond the diffusive regime] 25 November - 29 November 2024 (Invited talk: Hamiltonian Monte Carlo vs. event-chain Monte Carlo: Synopsis, benchmarks, prospects).
 +* University of Oxford (UK), Research stay 15 October - 11 December 2024 (Visiting Professor at the Department of Physics).
 +* Beg Rohu, Brittany (France), Summer School Concepts and Methods of Statistical Physics" 3 - 15 June 2024 (Lecture course: [[BegRohu_Lectures_2024|The second Markov-chain revolution]])
* New York, NY (USA), D. E. Shaw Research, 28 May 2024 (Invited Seminar: [http://www.lps.ens.fr/%7Ekrauth/images/6/6a/DEShaw.pdf Lifted Markov chains---from solvable models to applications in chemical physics]) * New York, NY (USA), D. E. Shaw Research, 28 May 2024 (Invited Seminar: [http://www.lps.ens.fr/%7Ekrauth/images/6/6a/DEShaw.pdf Lifted Markov chains---from solvable models to applications in chemical physics])
* New York University (USA), Simons Center for Computational Physical Chemistry, 21 May 2024 (Seminar: [http://www.lps.ens.fr/%7Ekrauth/images/1/1a/NYU_Simons.pdf Lifted Markov chains---from solvable models to applications in chemical physics]) * New York University (USA), Simons Center for Computational Physical Chemistry, 21 May 2024 (Seminar: [http://www.lps.ens.fr/%7Ekrauth/images/1/1a/NYU_Simons.pdf Lifted Markov chains---from solvable models to applications in chemical physics])

Current revision

50px
Werner Krauth
Laboratoire de Physique
École normale supérieure
24 rue Lhomond
75005 Paris
France
werner.krauth@ens.fr


CNRS Research Director - Theoretical Physics (Directeur de recherche CNRS - classe exceptionnelle).

Visiting Professor in Physics - University of Oxford (2023 - 26).

Keeley Visiting Fellow - Wadham College (Oxford, UK) (October 2023 - March 2024).

Distinguished Visiting Professor, Simons Center for Computational Physical Chemistry, New York University, New York (NY, USA) - April, May 2024

From January to June 2018, I was the 2018 Martin-Gutzwiller fellow at the Max-Planck-Institute for the Physics of Complex Systems in Dresden (Germany).

In 2018, I was a recipient of the Humboldt research award (Alexander von Humboldt Foundation).


Contents

[edit]

Oxford Lectures 2026

Since 2023, I have enjoyed myself tremendously as Visiting Professor in Physics at the University of Oxford where, again this year, I spend several months. I'm heavily engaged in research within an incredibly active and collaborative environment. I also give a set of public lectures on Algorithms and Computations in theoretical physics (see the announcement for a syllabus). Lecture notes are available, and will be updated "with the flow of the water", as we say in French.

I am very grateful to the Department and the University to have arranged for me to lecture on one of my favorite subjects, and also to have made these lectures "public". Anyone can attend: Students at the Oxford Physics department (or not), postdocs (or not), young and old, from all walks of life. This year's lectures start on 20 January 2026, and they take place every Tuesday afternoon at 2pm until 10 March 2026.

Public Lectures at University of Oxford, Tuesdays 2-4pm, 20 January through 10 March 2026
Public Lectures at University of Oxford, Tuesdays 2-4pm, 20 January through 10 March 2026


[edit]

Research over the ages

A (big) number of months ago, in 1988-89 (sic!), we were fascinated by a certain problem in the then new field of neural-networks research, namely the binary perceptron. The question was about the storage capacity of the now famous Hopfield model that, in a certain continuous case, had long been proven to be 2N, a result due to Thomas M. Cover (1965) and reinterpreted by E. Gardner (1987). We found this result depressing, as it stated that you needed (with, here on the website, a few shortcuts) N real numbers in order to store 2N single bits 0 and 1. This is like paying N gold coins (floats) to buy 2N copper dimes (single bits), clearly a bad deal. So we were very interested in finding out what would happen in the binary perceptron where, instead of N real numbers (the weights of one row of the Hopfield net) you had N bits (the weights of the binary Hopfield net). Together with Manfred Opper, who then visited ENS (where I did my thesis) from the University of Giessen in Germany, we wrote a computational paper, which quite clearly showed that the capacity was reduced from 2 (Cover's result) to a strange number very close to 0.82. At the time, we were quite proud of the two tricks which made our approach work namely, on the one hand, that we approximated the binary patterns with Gaussians patterns (which greatly improved the finite-size scaling) and, on the other hand, that we used the Gray code for a certain enumeration job. A few months later, again in 1989, with Marc Mézard, we conjectured, based on a one-step replica-symmetry-breaking calculation, that the critical capacity had to be equal to 0.833, a known function. In the conclusion of our 1989 paper, we speculated that our solution might well be exact

... conclusions of a 1989 paper...
... conclusions of a 1989 paper...


As I mentioned above, this was in 1989, before the bicentennial celebration of the French Revolution and many other events. For a fair number of years (months, I should say), the question of the critical capacity of the binary perceptron fascinated physicists, mathematicians and computer scientists, as it had first fascinated us. But it always appeared that "some more work" was "needed". Then finally, early in 2024, a keystone paper was written by Brice Huang, a MIT graduate student in Mathematics. He completed an enormous body of previous works, actually showed that our 0.833 had been correct all along. Brice was awarded the very prestigious Machtey award for best student paper in 2024. Bravo, congratulations, and celebrations, Brice --- the long wait was worth it and, indeed, "some more analytical work had been required..."!

[edit]

Milestone Research

A 2009 paper introducing the event-chain Monte Carlo algorithm was the object of a commentary, in 2026, by Prof E.A.J.F. Peters, from the Eindhoven University of Technology, The Netherlands. The statement of significance of the commentary starts with: "The seminal 2009 paper by Bernard, Krauth, and Wilson marked a paradigm shift in Monte Carlo sampling. By abandoning the restrictive condition of detailed balance in favor of the more fundamental principle of global balance..."

A 2013 paper, on a first-order transition in two dimensions, by a collaboration on three continents (!) that I published a few years ago in Physical Review E together with M. Engel, J. A. Anderson, S. C. Glotzer, M. Isobe, and E. P. Bernard, was chosen as the milestone article for 2013 by the journal's editorial board. This 2013 paper confirmed research published in 2011, in Physical Review Letters, with Etienne Bernard, on what really goes on in two-dimensional melting. See here for the story of the paper.

[edit]

Video recordings of research talks

Hard-disk packings and two phase transitions of two-dimensional particle systems Invited talk at the workshop "Optimal Point Configurations on Manifolds", Erwin Schrödinger International Institute for Mathematics and Physics, University of Vienna, Vienna (Austria), 2021 (online talk)

Fast stochastic sampling with irreversible, totally asymmetric, Markov chains (Invited talk at Institute for Pure & Applied Mathematics, UCLA, Los Angeles (USA), 2017)

[edit]

Current research

Go to Past Research Notices

I am deeply interested in statistical and condensed-matter physics, often in connection to computation and algorithms. Current interests are in hard spheres, mainly the melting transition in two-dimensional disks and in two-dimensional melting, bosons (in collaboration with the experimental groups at ENS), and the theory of convergence and of coupling in Markov chains. Recent work in my research group has led to the redefinition of the dominant Markov-chain Monte Carlo paradigm, namely the Metropolis algorithm. This has already allowed us to propose powerful algorithms for particle systems, continuous spin models and long-range systems, and to obtain important physical results. Research on the beyond-Metropolis paradigm, together with applications in classical and quantum physics and its interfaces will likely be a focus of my research activity in the next few years.

[edit]

Velocity Trapping in the Lifted TASEP and the True Self-Avoiding Random Walk

In 2024/25, three of my mathematician friends, Brune Massoulié, Clément Erignoux, Cristina Toninelli, (from ENS Paris, from University Paris Dauphine, and from INRIA Lyon) and I attempted to understand the astonishingly fast convergence of non-reversible Markov chains, represented by the lifted TASEP, a system of N hard core particles on a one-dimensional lattice of L sites, a model that I discuss below in more detail. It was already clear from previous work that the lifted TASEP possessed a pointer, whose velocity was zero at a certain parameter alpha = N/L, in other words, the overall density. The velocity was negative for smaller densities and larger for larger ones. The first key insight of our paper that resulted from this work was that the pointer could not possibly know how many particles N there were exactly on a lattice of L (imagine L=100.000.000.000). This brought us to a discussion in terms of the local density. Whereever the local density was a bit larger than the average N/L, the pointer would move forward, and it would move backwards at slightly lower local density. There is thus an evident density-velocity correlation that is absent in usual statistical mechanics. After a few intense work sessions (online between New York or Oxford, Paris and Lyon, and then in person at the ENS Math department), we came up with the concept of "velocity trapping" which, correctly formulated and mathematically formalized, gave a manuscript which was accepted for publication in Physical Review Letters, in 2025, not very long after we had submitted it. The paper contains a second key insight, namely the connection of the non-reversible Markov chains and, in particular, the lifted TASEP, to the wide field of True Self-avoiding random walks. The story is fascinating and it follows seminal observations by my friend A. C. "Tony" Maggs (ESPCI Paris) but is a bit complicated to explain on this website. You're invited to take a look at the original paper.

[edit]

Fast, approximation-free molecular simulation of the SPC/Fw water model using non-reversible Markov chains

Many fields of computational science concern the sampling of configurations x from a distribution pi(x) which can often be written as pi(x) = exp[-beta E(x)] (that is, as a Boltzmann distribution). The configuration x then refers to the positions of thousands or millions of atoms with complicated, often long-ranged, interactions. Over the years, I have been interested in sampling methods which do not evaluate the energy E (or the difference of energies, or the gradient of E) in order to sample pi(x) = exp[-beta E(x)]. This is possible because of our use of the factorized Metropolis filter within the framework of the event-chain Monte Carlo algorithm. In July 2024, finally, the manuscript ["Fast, approximation-free molecular simulation ... "] on which I had worked together with Philipp Höllmer and A. C. Maggs was published in the Journal "Scientific Reports". It actually proves that one can simulate large water systems (in our case, the SPC/Fw water model) without any approximation. We generate millions of samples, but absolutely do not know what is the energy of our configurations.

The remarkable efficiency of our simulation method is rooted in three paradoxes. First, the Markov process is non-reversible (that is, effectively out-of-equilibrium), yet its steady state coincides with the equilibrium Boltzmann distribution. Second, the Boltzmann distribution exp(−βU) is sampled without any approximation and with great efficiency although the total potential U and its derivatives, the forces, are never evaluated. This sidesteps all the problems with limited-precision calculations of energies and forces. The third paradox is the bundling of O(N) independent decisions to interrupt the straight-line trajectory of the piecewise-deterministic Markov process into an expression that can be evaluated in constant time. The paper is openly accessible, and even all the computer code has been rendered open-source.


[edit]

Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains

In recent years, my colleagues and I have worked on a multitude of computational algorithms which improve on the classical methods. Specifically, we have worked on Monte Carlo algorithms based on non-reversible Markov chains. Such algorithms have had successes in applications but are generally difficult to analyze, resulting in a scarcity of exact results. In a recent manuscript Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains, now published in Physical Review X with my colleague Fabian Essler (Oxford), we introduce the “lifted” TASEP (totally asymmetric simple exclusion process) as a paradigm for non-reversible Markov chains. Our model can be viewed as a second-generation lifting of the reversible Metropolis algorithm on a one-dimensional lattice and is exactly solvable by an unusual kind of coordinate Bethe ansatz. We establish the integrability of the model and present strong evidence that the lifting leads to relaxation on shorter timescales than in the KPZ (Kardar–Parisi–Zhang) universality class.

Here the "Popular Summary" that accompanied our paper:

Markov-chain Monte Carlo (MCMC) algorithms formulate the sampling problem for complex probability distributions as a simulation of fictitious physical systems in equilibrium, where all motion is diffusive and time reversible. But nonreversible algorithms can, in principle, sample distributions much more efficiently. In recent years, a class of “lifted” Markov chains has implemented this idea in practice, but the resulting algorithms are extremely difficult to analyze. In this work, we introduce an exactly solvable paradigm for nonreversible Markov chains.

Our paradigm, which we term the lifted totally asymmetric simple exclusion process (TASEP), describes a particular type of nonreversible dynamics for particles on a one-dimensional lattice. We show that this dynamics allows for polynomial speedups in particle number compared to the famous Metropolis MCMC algorithm. The lifted-TASEP dynamics is, in fact, faster than that of any other known class of models. To arrive at our conclusions, we combine exact methods from the theory of integrable models with extensive numerical simulations. In particular, we prove that the lifted TASEP is integrable and determine the scaling of its relaxation and mixing times with system size.

Our work opens the door to obtaining mathematically rigorous results for speedups of nonreversible MCMC algorithms, and more generally, of lifted Markov chains arising in interacting many-particle systems.



Continue with Past Research Notices

[edit]

Upcoming events

Here is the schedule of past events

[edit]

Text book

Cover of a book I wrote in 2006 Here is the book's website
Cover of a book I wrote in 2006 Here is the book's website


[edit]

Interview, Popular story, video conference

2012 interview at Ecole normale supérieure (in French)

CNRS special on our work on two-dimensional melting (June 2013) (in French) in Japanese (!)

2012 Conference on time's arrow (video, in French) in the framework of the Festival "acceleration" Sacre Doctoral school

Video presentation of the Massive Open Online course at ENS

Editorial "Coming home from a MOOC", about teaching a Massive Open Online Course (MOOC) (October 2014)

Grande conférence scientifique "Du déterminisme au stochastique : du hasard classique à l'aléatoire quantique", for the incoming science students at ENS (in French, September 2015)

"The largest Lecture Hall in the world", Article in "Physik Journal" on MOOCs, and in particular on my own MOOC (in German, March 2017)

[edit]

A picture book of algorithms

Direct-sampling algorithm for ideal bosons in a trap (see article with M. Holzmann). Adapted for interacting bosons, this algorithm was used in a variety of articles.
Direct-sampling algorithm for ideal bosons in a trap (see article with M. Holzmann). Adapted for interacting bosons, this algorithm was used in a variety of articles.
Event-chain Monte Carlo algorithm for hard spheres and related systems (see article with E. P. Bernard and D. B. Wilson, including Python implementation). This (fantastic) algorithm, about two orders of magnitude faster than local Monte Carlo, was used in our discovery of the first-order liquid-hexatic phase transition in hard disks. The method can be generalized to continuous potentials, and we used it to map out the phase diagrams of soft-disk systems. Look here for an implementation of the event-chain algorithm
Event-chain Monte Carlo algorithm for hard spheres and related systems (see article with E. P. Bernard and D. B. Wilson, including Python implementation). This (fantastic) algorithm, about two orders of magnitude faster than local Monte Carlo, was used in our discovery of the first-order liquid-hexatic phase transition in hard disks. The method can be generalized to continuous potentials, and we used it to map out the phase diagrams of soft-disk systems. Look here for an implementation of the event-chain algorithm


Exact diagonalization algorithm for Dynamical mean field theory (see article with M. Caffarel). This algorithm has been instrumental in our discovery of a first-order Mott transition in the Hubbard model in infinite dimensions. Much of our early work in the field is written up in our review with Georges, Kotliar, and Rozenberg
Exact diagonalization algorithm for Dynamical mean field theory (see article with M. Caffarel). This algorithm has been instrumental in our discovery of a first-order Mott transition in the Hubbard model in infinite dimensions. Much of our early work in the field is written up in our review with Georges, Kotliar, and Rozenberg
Rejection-free cluster algorithm for dimers (see article with R. Moessner). This algorithm was used for our discovery of a critical phase in three-dimensional dimer models (paper with Huse, Sondhi, and Moessner). Note that dimers flip about a symmetry axis between one valid configuration and another.
Rejection-free cluster algorithm for dimers (see article with R. Moessner). This algorithm was used for our discovery of a critical phase in three-dimensional dimer models (paper with Huse, Sondhi, and Moessner). Note that dimers flip about a symmetry axis between one valid configuration and another.
Alder and Wainwright's event-driven Molecular Dynamics algorithm (1957). (Animation by Maxim Berman).
Alder and Wainwright's event-driven Molecular Dynamics algorithm (1957). (Animation by Maxim Berman).


Retrieved from "http://www.lps.ens.fr/~krauth/index.php/Main_Page"
Personal tools